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