B.Little Elephant And Array

Revision en1, by gsmcoder97, 2016-06-02 10:17:11

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

Tags sqrt_decomposition, sqrt-decomposition

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English gsmcoder97 2016-06-02 10:17:11 1544 Initial revision (published)