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; }
Link
And try to paste your code nicely.