fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define N 50005
  4. #define B 225
  5. int F1[N/B+5][N],F2[N/B+5][N];
  6. int n,m;
  7. int a[N],sum[N],temp[N];
  8. int cnt1=1;
  9. void precalc()
  10. {
  11.     for(int i=0;i<=N/B;i++){
  12.         int l=i*B;
  13.         if(l>n)
  14.             break;
  15.         for(int r=l;r<=n;r++)
  16.             temp[sum[r]]=-1;
  17.  
  18.         int tmp=0;
  19.  
  20.         for(int r=l;r<=n;r++){
  21.             if(temp[sum[r]]==-1){
  22.                 temp[sum[r]]=r;
  23.             }
  24.             else
  25.                 tmp=max(tmp,r-temp[sum[r]]);
  26.             F1[i][r]=tmp;
  27.             //printf("%d %d = %d\n",i,r,tmp);
  28.         }
  29.     }
  30.     for(int i=0;i<=N/B;i++){
  31.         int r=i*B;
  32.         if(r>n)
  33.             break;
  34.         int tmp=0;
  35.         for(int l=0;l<r;l++){
  36.             temp[sum[l]]=-1;
  37.         }
  38.         for(int l=r-1;l>=0;l--){
  39.             if(temp[sum[l]]==-1)
  40.                 temp[sum[l]]=l;
  41.             else
  42.                 tmp=max(tmp,temp[sum[l]]-l);
  43.             F2[i][l]=tmp;
  44.             //printf("%d %d = %d\n",i,l,tmp);
  45.         }
  46.     }
  47. }
  48. int solve(int l,int r)
  49. {
  50.     int ll=(l+B-1)/B;
  51.     int rr=r/B;
  52.     int ans=0;
  53.     if(ll+1<rr){
  54.  
  55.     ans=max(ans,max(F1[ll][r],F2[rr][l-1]));
  56.     for(int i=l-1;i<=ll*B;i++)
  57.         temp[sum[i]]=-1;
  58.     for(int i=r;i>=rr*B-1;i--)
  59.         temp[sum[i]]=-1;
  60.     for(int i=l-1;i<=ll*B;i++){
  61.         if(temp[sum[i]]==-1){
  62.             temp[sum[i]]=i;
  63.         }
  64.     }
  65.     int tmp=0;
  66.     for(int i=r;i>=rr*B-1;i--){
  67.         if(temp[sum[i]]!=-1){
  68.         tmp=max(tmp,i-temp[sum[i]]);
  69.        // printf("i = %d temp[sum[]] = %d\n",i,temp[sum[i]]);
  70.         }
  71.     }
  72.     // printf("here %d %d\n",ll*B,rr*B);
  73.     //printf("tmp = %d\n",tmp);
  74.     ans=max(tmp,ans);
  75.     }
  76.     else
  77.     {
  78.         for(int i=l-1;i<=r;i++)
  79.             temp[sum[i]]=-1;
  80.         int tmp=0;
  81.         for(int i=l-1;i<=r;i++){
  82.             if(temp[sum[i]]==-1)
  83.                 temp[sum[i]]=i;
  84.             else
  85.                 tmp=max(tmp,i-temp[sum[i]]);
  86.         }
  87.         ans=tmp;
  88.     }
  89.     return ans;
  90. }
  91. int main()
  92. {
  93.     //freopen("input.txt","r",stdin);
  94.     //freopen("output1.txt","w",stdout);
  95.     scanf("%d %d",&n,&m);
  96.     for(int i=1;i<=n;i++){
  97.         scanf("%d",&a[i]);
  98.         sum[i]=sum[i-1]+a[i];
  99.     }
  100.     precalc();
  101.     memset(temp,-1,sizeof(temp));
  102.     while(m--){
  103.         int l,r;
  104.         scanf("%d %d",&l,&r);
  105.         if(l>r)
  106.             swap(l,r);
  107.         int ans=solve(l,r);
  108.         printf("%d\n",ans);
  109.          cnt1++;
  110.     }
  111. }
  112.  
  113.  
Success #stdin #stdout 0s 92352KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/ZXI3f7
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!