### NAMELESS's blog

By NAMELESS, history, 23 months ago, ,

Hello everyone,

I am trying to solve this problem. If I can build the LCP array with O(n) complexity I can easily solve it. But building LCP array requires suffix array. I know the O(n*logn*longn) algorithm. But It will give me TLE in this problem. I need the O(n) algorithm to build suffix array. I searched for it and get a paper which is too complex to understand for me. Can anyone give me a simple and well explained tutorial to build suffix array with O(n) time? It will be great help for me.

Thank you.

• +9

By NAMELESS, history, 2 years ago, ,

Hello Everyone,

It was known to me that lookup time in unordered_map is faster than map in C++. When I have to lookup frequent than insertion I should use unordered_map. In this problem I used unordered_map because in my implementation lookup is more frequent than insertion. But I got TLE. In my implementation with map I got accepted. what is wrong here? Any explanation will be helpful.

Thank you.

• +12

By NAMELESS, history, 2 years ago, ,

I am trying to solve this problem. There is a tutorial but for me its not so clear. You can see that I am green. For me the state is [numberOfProgrammer][numberOfLine][maxBug] which is 500*500*500. The tutorial has a solution with state 2*500*500. It is very hard for me to understand the state elimination. Someone please explain the solution so that I(as a green) can understand.

• +8

By NAMELESS, history, 2 years ago, ,

Hello,

I am trying to solve this problem and getting TLE, and I think my code is the best thing I can do. Please help me solve the problem by any efficient idea or optimizing my code:

#include <bits/stdc++.h>

using namespace std;

#define MX 5000005
#define M 100000007
#define LL long long
#define dbg(x) cout<<#x<<" = "<<x<<"\n"

int n;
LL cnt[MX];
int b[MX];

int main(){
while(cin>>n){
if(n==0) break;
memset(b,0,sizeof(b));
for(int i=n,v=1;i>1;i--,v++){
cnt[i]=v;
}
for(int i=2;i<=n;i++){
if(b[i]==0){
for(int j=i*2;j<=n;j+=i){
b[j]=1;
int t=j;
int div=0;
while(t%i==0){
div++;
t/=i;
}
cnt[i]+=cnt[j]*div;
}
}
}
LL ans=1;
for(int i=2;i<=n;i++){
if(b[i]==0){
ans=(ans*(cnt[i]+1))%M;
}
}
printf("%lld\n",ans);
}
}


• -3

By NAMELESS, history, 3 years ago, ,

i don't know what is wrong with my idea. I tried many times but still wrong answer. can anyone tell me what is wrong?

• -9

By NAMELESS, history, 3 years ago, ,

KQUERY

How can i optimize my code?

#include <bits/stdc++.h>

using namespace std;

int n, m, a[30005];
int bs;
vector<int> block[300];

int sqrtDecomposition(int l, int r, int v){
if(l / bs == r / bs){
int cnt = 0;
for(int i = l; i <= r; i++){
if(a[i] > v) cnt++;
}
return cnt;
}

int cnt = 0;
for(int i = l; i / bs == l / bs; i++){
if(a[i] > v) cnt++;
}
for(int i = r; r / bs == i / bs; i--){
if(a[i] > v) cnt++;
}
for(int i = l / bs + 1; i < r / bs; i++){
cnt += (block[i].end() - upper_bound(block[i].begin(), block[i].end(), v));
}
return cnt;
}

int main(){
cin >> n;
for(int i = 0; i < n; i++){
scanf("%d", a + i);
}
bs = sqrt(n);
for(int i = 0; i < n; i++){
block[i/bs].push_back(a[i]);
}
for(int i = 0; i < 300; i++){
sort(block[i].begin(), block[i].end());
}
cin >> m;
for(int i = 0; i < m; i++){
int l, r, v;
scanf("%d %d %d", &l, &r, &v);
l--; r--;
int ans = sqrtDecomposition(l, r, v);
printf("%d\n", ans);
}
}