fork(3) download
  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
stdin
swagmaster
stdout
Standard output is empty