fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define REP(i,n) for (int i = 1; i <= n; i++)
  3. #define mod 1000000007
  4. #define pb push_back
  5. #define ff first
  6. #define ss second
  7. #define ii pair<int,int>
  8. #define vi vector<int>
  9. #define vii vector<ii>
  10. #define lli long long int
  11. #define INF 1000000000
  12. #define BLK 1000
  13. #define endl '\n'
  14. const double PI = 3.141592653589793238460;
  15. typedef std::complex<double> Complex;
  16. typedef std::valarray<Complex> CArray;
  17.  
  18. using namespace std;
  19. struct query{
  20. 	int l;
  21. 	int r;
  22. 	int i;
  23. };
  24.  
  25. query Q[100001];
  26. int ar[100001];
  27. int ans[100001];
  28. int B[100001];
  29. int fre[200005];
  30. set<ii> st;
  31.  
  32. bool comp(query a, query b)
  33. {
  34. 	if(B[a.l] != B[b.l])
  35. 	return B[a.l] < B[b.l];
  36.  
  37. 	return a.r < b.r;
  38. }
  39.  
  40. void add(int idx)
  41. {
  42. 	int ele = ar[idx];
  43. 	fre[ele]++;
  44. 	if(fre[ele] > 1)
  45. 	{
  46. 		st.erase({-(fre[ele]-1) , ele});
  47. 	}
  48. 	st.insert({-fre[ele] , ele});
  49. }
  50.  
  51. void remove(int idx)
  52. {
  53. 	int ele = ar[idx];
  54. 	fre[ele]--;
  55.  
  56. 	st.erase({-(fre[ele]+1) , ele});
  57. 	if(fre[ele] > 0)
  58. 	st.insert({-(fre[ele]) , ele});
  59. }
  60.  
  61. int getMostFre()
  62. {
  63. 	ii p = *st.begin();
  64. 	return -p.ff;
  65. }
  66.  
  67. int main()
  68. {
  69. 	ios::sync_with_stdio(false);
  70. 	cin.tie(0);
  71. 	cout.tie(0);
  72. 	REP(i , 100001) B[i-1] = i / BLK;
  73. 	int n , q;
  74. 	while(1)
  75. 	{
  76. 		cin>>n;
  77. 		if(n == 0) break;
  78. 		cin>>q;
  79.  
  80. 		REP(i , n) cin>>ar[i-1];
  81.  
  82. 		int cnt = 1;
  83. 		int pre = ar[0];
  84. 		for(int i=0;i<n;i++)
  85. 		if(ar[i] == pre)
  86. 		ar[i] = cnt;
  87. 		else
  88. 		cnt++ , pre = ar[i] , ar[i] = cnt;
  89.  
  90. 		REP(i , cnt) fre[i] = 0;
  91. 		REP(i , q)
  92. 		{
  93. 			cin>>Q[i-1].l>>Q[i-1].r , Q[i-1].i = i;
  94. 			Q[i-1].l-- , Q[i-1].r--;
  95. 		}
  96. 		sort(Q , Q+q , comp);
  97. 		st.clear();
  98. 		int ML = 0 , MR = -1;
  99. 		REP(i , q)
  100. 		{
  101. 			int L = Q[i-1].l;
  102. 			int R = Q[i-1].r;
  103.  
  104. 			while(ML > L)
  105. 			ML-- , add(ML);
  106.  
  107. 			while(MR < R)
  108. 			MR++ , add(MR);
  109.  
  110. 			while(ML < L)
  111. 			remove(ML) , ML++;
  112.  
  113. 			while(MR > R)
  114. 			remove(MR) , MR--;
  115.  
  116. 			ans[Q[i-1].i] = getMostFre();
  117. 		}
  118.  
  119. 		REP(i , q)
  120. 		cout<<ans[i]<<endl;
  121. 	}
  122.  
  123. }
  124.  
Success #stdin #stdout 0s 4316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/HNHBOS
Spoj FREQUENT : Mo's TLE
language:
C++14 (gcc 8.3)
created:
4 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!