Блог пользователя gsmcoder97

Автор gsmcoder97, история, 8 лет назад, По-английски

I started coding square root decomposition myself and submitted my code for Little Elephant And Array(http://mirror.codeforces.com/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

  • Проголосовать: нравится
  • -1
  • Проголосовать: не нравится

»
8 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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