fork(3) 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 210000
  8. inline int scan(){
  9.     char c = getchar_unlocked();
  10.     int x = 0;
  11.     bool b=0;
  12.     while(c<'0'||c>'9'){
  13.         if(c=='-'){
  14.             b=1;
  15.         }
  16.         c=getchar_unlocked();
  17.     }
  18.     while(c>='0'&&c<='9'){
  19.         x=(x<<1)+(x<<3)+c-'0';
  20.         c=getchar_unlocked();
  21.     }
  22.     if(b){
  23.         return -x;
  24.     }
  25.     return x;
  26. }
  27. #define index second.second.second
  28. #define lef second.second.first
  29. #define rig second.first
  30. #define blok first
  31. int n,q;
  32. 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
  33. int freq[N]={0};
  34. int counter[N]={0};
  35. int arr[N];
  36. int ans[N]={0};
  37. int curl=1,curr=0;
  38. int tempans;
  39. void process(pair<int,pair<int,pair<int,int> > > a){
  40.     int l=-a.lef;
  41.     int r=-a.rig;
  42.     int indice=a.index;
  43.    // cout<<l<<" "<<r<<" "<<indice<<endl;
  44.     //1 1 3 3 3 3 5 12 12 12  , 2 ,3
  45.     while(r>curr){//add
  46.         curr++;
  47.         int val=arr[curr];
  48.         int c=freq[val];
  49.         counter[c]--;
  50.         freq[val]++;
  51.         counter[freq[val]]++;
  52.         tempans=max(tempans,freq[val]);
  53.       //  cout<<"r add ";
  54.       //  cout<<val<<" "<<freq[val]<<" "<<counter[freq[val]]<<" "<<tempans<<endl;
  55.     }
  56.     while(l>curl){//remove
  57.         int val=arr[curl];
  58.         counter[freq[val]]--;
  59.         freq[val]--;
  60.         counter[freq[val]]++;
  61.         curl++;
  62.         while(counter[tempans]==0){
  63.             tempans--;
  64.         }
  65.        // cout<<"l remove ";
  66.        // cout<<val<<" "<<freq[val]<<" "<<counter[freq[val]]<<" "<<tempans<<endl;
  67.     }
  68.     while(l<curl){//add
  69.         curl--;
  70.         int val = arr[curl];
  71.         int c = freq[val];
  72.         counter[c]--;
  73.         freq[val]++;
  74.         counter[freq[val]]++;
  75.         tempans=max(tempans,freq[val]);
  76.        // cout<<"l add ";
  77.        // cout<<val<<" "<<freq[val]<<" "<<counter[freq[val]]<<" "<<tempans<<endl;
  78.     }
  79.     while(r<curr){//remove
  80.         int val=arr[curr];
  81.         counter[freq[val]]--;
  82.         freq[val]--;
  83.         counter[freq[val]]++;
  84.         curr--;
  85.         while(counter[tempans]==0){
  86.             tempans--;
  87.         }
  88.        // cout<<"r remove ";
  89.        // cout<<val<<" "<<freq[val]<<" "<<counter[freq[val]]<<" "<<tempans<<endl;
  90.     }
  91.     ans[indice]=tempans;
  92.     //cout<<l<<" "<<r<<" "<<counter[tempans]<<endl;
  93. }
  94. int main(){
  95.     while(1){
  96.         n=scan();
  97.         if(n==0){
  98.             break;
  99.         }
  100.         int sqn=sqrt(n);
  101.         memset(counter,0,sizeof(int)*N);
  102.         memset(freq,0,sizeof(int)*N);
  103.         counter[0]=n;
  104.         curl=1;
  105.         curr=0;
  106.         tempans=0;
  107.         q=scan();
  108.         for(int i=1;i<=n;i++){
  109.             arr[i]=scan();
  110.             arr[i]+=100000;
  111.         }
  112.         for(int i=1;i<=q;i++){
  113.             int l=scan(),r=scan();
  114.             int pos=l/sqn;
  115.             pair<int,pair<int,pair<int,int> > > temp;
  116.             temp.blok = -pos;
  117.             temp.rig = -r;
  118.             temp.lef = -l;
  119.             temp.index = i;
  120.             PQ.push(temp);
  121.         }
  122.         while(!PQ.empty()){
  123.             pair<int,pair<int,pair<int,int> > >  x = PQ.top();
  124.             PQ.pop();
  125.             process(x);
  126.         }
  127.         for(int i=1;i<=q;i++){
  128.             printf("%d\n",ans[i]);
  129.         }
  130.     } 
  131. }
Time limit exceeded #stdin #stdout 5s 6380KB
comments (?)
stdin
copy 
swagmaster
stdout
copy 
Standard output is empty
https://ideone.com/b7rbPr
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

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!