fork(2) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define author rajat1603
  4. #define mod 1000000007
  5. #define pb push_back
  6. #define mp make_pair
  7. #define N 100002
  8. #define SN 400000
  9. #define SQN 327
  10. inline int scan(){
  11.     char c = getchar_unlocked();
  12.     int x = 0;
  13.     bool b=0;
  14.     while(c<'0'||c>'9'){
  15.         if(c=='-'){
  16.             b=1;
  17.         }
  18.         c=getchar_unlocked();
  19.     }
  20.     while(c>='0'&&c<='9'){
  21.         x=(x<<1)+(x<<3)+c-'0';
  22.         c=getchar_unlocked();
  23.     }
  24.     if(b){
  25.         return -x;
  26.     }
  27.     return x;
  28. }
  29. #define index second.second.second
  30. #define lef second.second.first
  31. #define rig second.first
  32. #define blok first
  33. int n,m=100002,k;
  34. int leftmost[N]={0},rightmost[N]={0},nextright[N]={0},nextleft[N]={0},templeft[N],tempright[N];
  35. int sqn;
  36. priority_queue<pair<int,pair<int,pair<int,int> > > > PQ;//first will have l/sqn , second.first will have right , second.second.first will have left and second.second.second will have index
  37. int freq[N]={0};
  38. int arr[N];
  39. int segtree[SN];
  40. int ans[N];
  41. int curl=1,curr=0;
  42. int posintree[N];
  43. void build(int l,int r,int node){
  44.     if(l==r){
  45.         posintree[l]=node;
  46.         return;
  47.     }
  48.     int lc=node<<1;
  49.     int rc=lc|1;
  50.     int mid = (l+r)>>1;
  51.     build(l,mid,lc);
  52.     build(mid+1,r,rc);
  53. }
  54. void update(int inde,int val){
  55.     int x=posintree[inde];
  56.     segtree[x]=val;
  57.     while(x){
  58.         x>>=1;
  59.         int lc=x<<1;
  60.         int rc=lc|1;
  61.         segtree[x]=max(segtree[lc],segtree[rc]);
  62.     }
  63. }
  64. void process(pair<int,pair<int,pair<int,int> > > a){
  65.     int l=-a.lef;
  66.     int r=-a.rig;
  67.     int indice=a.index;
  68.     //cout<<l<<" "<<r<<endl;
  69.     //3,5 to 5,6 , 4 5 6 6 5 7 4
  70.     while(curr>r){
  71.         int val=arr[curr];
  72.         rightmost[val]=nextleft[curr];
  73.         if(nextleft[curr]==0){
  74.             rightmost[val]=curr;
  75.         }
  76.         update(val,rightmost[val]-leftmost[val]);
  77.         curr--;
  78.     }
  79.     while(r>curr){
  80.         curr++;
  81.         int val=arr[curr];
  82.         rightmost[val]=curr;
  83.         if(leftmost[val]==0){
  84.             leftmost[val]=curr;
  85.         }
  86.         int nmax = rightmost[val]-leftmost[val];
  87.         update(val,nmax);
  88.         //cout<<"curr++ "<<val<<" "<<nmax<<endl;
  89.     }
  90.     while(l>curl){
  91.         int val=arr[curl];
  92.         leftmost[val]=nextright[curl];
  93.         if(nextright[curl]==0){
  94.             rightmost[val]=0;
  95.         }
  96.         update(val,rightmost[val]-leftmost[val]);
  97.         curl++;
  98.     }
  99.     while(l<curl){
  100.         curl--;
  101.         int val=arr[curl];
  102.         leftmost[val]=curl;
  103.         if(rightmost[val]==0){
  104.             rightmost[val]=curl;
  105.         }
  106.         update(val,rightmost[val]-leftmost[val]);
  107.        // cout<<"curl-- "<<val<<" "<<nmax<<endl;
  108.     } 
  109.     ans[indice]=segtree[1];
  110.     if(ans[indice]<0){
  111.         ans[indice]=0;
  112.     }
  113. }
  114. int main(){
  115.     arr[1]=50001;
  116.     n=scan(),k=scan();
  117.     sqn=sqrt(n+1);
  118.     build(1,100002,1);
  119.     for(int i=1;i<=n;i++){
  120.         arr[i+1]=arr[i]+scan();
  121.     }
  122.     n++;
  123.     for(int i=1;i<=n;i++){
  124.         int cur = arr[i];
  125.         nextleft[i]=templeft[cur];
  126.         templeft[cur]=i;
  127.     }
  128.     for(int i=n;i>=1;i--){
  129.         int cur=arr[i];
  130.         nextright[i]=tempright[cur];
  131.         tempright[cur]=i;
  132.     }
  133.     int ma=0;
  134.     for(int i=1;i<=k;i++){
  135.         int l=scan(),r=scan()+1;
  136.         int pos=l/sqn;
  137.         pair<int,pair<int,pair<int,int> > > temp;
  138.         temp.blok = -pos;
  139.         temp.rig = -r;
  140.         temp.lef = -l;
  141.         temp.index = i;
  142.         PQ.push(temp);
  143.     }
  144.     while(!PQ.empty()){
  145.         pair<int,pair<int,pair<int,int> > >  x = PQ.top();
  146.         PQ.pop();
  147.         process(x);
  148.     }
  149.     for(int i=1;i<=k;i++){
  150.         printf("%d\n",ans[i]);
  151.     }
  152. }
Time limit exceeded #stdin #stdout 5s 8616KB
comments (?)
stdin
copy 
SO GOOD ALGORITHM
stdout
copy 
Standard output is empty
https://ideone.com/YayNX7
language:
C++ (gcc 8.3)
created:
9 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!