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