asvikr's blog

By asvikr, 10 years ago, In English

Why my code give wrong answer for problem z-query ?

my approach is here

define N 50005

define B 225

int F1[B+5][N],F2[B+5][N]; int n,m; int a[N],sum[N],temp[N]; void precalc() { for(int i=0;i<B;i++){ int l=i*B; if(l>n) break; for(int r=l;r<=n;r++) temp[sum[r]]=-1;

int tmp=0;

    for(int r=l;r<=n;r++){
        if(temp[sum[r]]==-1){
            temp[sum[r]]=r;
        }
        else
            tmp=max(tmp,r-temp[sum[r]]);
        F1[i][r]=tmp;
       // printf("%d %d = %d\n",i,r,tmp);
    }
}
for(int i=0;i<B;i++){
    int r=i*B;
    if(r>n)
        break;
    int tmp=0;
    for(int l=0;l<r;l++){
        temp[sum[l]]=-1;
    }
    for(int l=r-1;l>=0;l--){
        if(temp[sum[l]]==-1)
            temp[sum[l]]=l;
        else
            tmp=max(tmp,temp[sum[l]]-l);
        F2[i][l]=tmp;
       // printf("%d %d = %d\n",i,l,tmp);
    }
}

}

int solve(int l,int r) { int ll=(l+B-1)/B; int rr=r/B; int ans=0; if(ll<rr){ ans=max(ans,max(F1[ll][r],F2[rr][l-1])); for(int i=l-1;i<=ll*B;i++) temp[sum[i]]=-1; for(int i=l-1;i<=ll*B;i++){ if(temp[sum[i]]==-1){ temp[sum[i]]=i; } }

for(int i=r;i>=rr*B;i--){
    if(temp[sum[i]]!=-1)
    ans=max(ans,i-temp[sum[i]]);
}
}
else
{
    for(int i=l-1;i<=r;i++)
        temp[sum[i]]=-1;
    int tmp=0;
    for(int i=l-1;i<=r;i++){
        if(temp[sum[i]]==-1)
            temp[sum[i]]=i;
        else
            tmp=max(tmp,i-temp[sum[i]]);
    }
    ans=tmp;
}
return ans;

}

int main() { scanf("%d %d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); sum[i]=sum[i-1]+a[i]; } precalc(); while(m--){ int l,r; scanf("%d %d",&l,&r); if(l>r) swap(l,r); int ans=solve(l,r); printf("%d\n",ans); } return 0; }

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it