gsmcoder97's blog

B.Little Elephant And Array
By gsmcoder97, history, 8 years ago, In English

I started coding square root decomposition myself and submitted my code for Little Elephant And Array(http://codeforces.net/contest/220/problem/B); however, I am getting compilation error. Is there some error in my code? How can I make it more optimal?

struct x{
    int ct[size1]; int mini, maxi;
};
x block[size1];
void cons(int n, int a[]){
    int p=floor(sqrt(n));
    for(int i=0;i<n;i++){block[i/p+1].ct[a[i]]++; block[i/p+1].mini=min(block[i/p+1].mini,a[i]); block[i/p+1].maxi=max(block[i/p+1].maxi,a[i]);}
}
void query(int l,int r,int n, int a[], int &ans){
    int p=floor(sqrt(n));
    int b1=(l-1)/p+1;
    int b2=(r-1)/p+1;
    //int ans=0;
    if(b1==b2){
        map<int,int> v;
        for(int i=(l-1);i<=(r-1);i++)v[a[i]]++;
        map<int,int>::iterator it=v.begin();
        for(;it!=v.end();it++)if(it->second==it->first)ans++;
    }
    else if(b1!=b2){
        map<int,int> v;
        for(int i=l;i<b1*p;i++)v[a[i]]++;
        for(int i=b1;i<b2;i++)for(int j=block[i].mini;j<=block[j].maxi;j++)v[j]+=block[i].ct[j];
        for(int i=b2*p;i<=r;i++)v[a[i]]++;
        map<int,int>::iterator it=v.begin();
        for(;it!=v.end();it++)if(it->second==it->first)ans++;
    }
}
int main(){
    int n,m; cin>>n>>m;
    int a[n]; for(int i=0;i<n;i++)cin>>a[i];
    cons(n,a);
    while(m--){
        int x,b; cin>>x>>b;
        int ans=0;
        query(x,b,n,a,ans); cout<<ans<<endl;
    }
    return 0;
}

Any help is appreciated. Thank you

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
8 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

In your code you have static array of structures. Each element of it has another static array with 100001 size. So size of your big array is 100001 * 100001, but you cannot create static array using so much memory. If you change "x block[size1]" to "vector< x > block(size1)", it doesn't get compilation error. But now it will get RT1 one, because 10 ** 10 memory is to much. I don't think this problem can be solved with sqrt decomposition with such limits.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I was trying to practice questions on square root decomposition. However, after reading your answer, I think you are right; however, is there any errors in my implementation of square root decomposition code(except for the exceeding memory)? Thanks

    → Reply