fork download 
  1. #pragma GCC optimize("O3")
  2. #pragma GCC optimize("Ofast")
  3. #pragma GCC optimize("unroll-loops")
  4. #pragma GCC target("avx,avx2,fma,sse2")
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long
  8. #define db double
  9. #define is insert
  10. #define pb push_back
  11. #define pii pair<int, int>
  12. #define pll pair<long long, long long>
  13. #define X first
  14. #define Y second
  15. #define vi vector<int>
  16. #define vpi vector<pair<int, int>>
  17. #define msi multiset<int>
  18. #define int long long
  19. const int m97 = (int)1e9+7;
  20. const int m83 = 998244353;
  21. const int N = 500005;
  22. const int K = 1000005;
  23. const int inf = (int)1e18;
  24.  
  25. //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  26.  
  27. struct query{
  28. 	int l, r, id, ans;
  29. };
  30.  
  31. int n, m;
  32. int cnt[K], a[N], block[N];
  33. int res[N];
  34. int B = sqrt(N);
  35. vector<query> q;
  36.  
  37. bool cmpmo(query a, query b){
  38. 	if(a.l / B != b.l / B){
  39. 		return a.l / B < b.l / B;
  40. 	}
  41. 	return a.r < b.r;
  42. }
  43.  
  44. void add(int x){
  45. 	if(cnt[a[x]]==1) block[(a[x]-1)/B]--;
  46.     cnt[a[x]]++;
  47.     if(cnt[a[x]]==1) block[(a[x]-1)/B]++;
  48. }
  49.  
  50. void remove(int x){
  51. 	if(cnt[a[x]]==1) block[(a[x]-1)/B]--;
  52.     cnt[a[x]]--;
  53.     if(cnt[a[x]]==1) block[(a[x]-1)/B]++;
  54. }
  55.  
  56. void solve(){
  57. 	cin >> n;
  58. 	for(int i=1; i<=n; i++){
  59. 		cin >> a[i];
  60. 	}
  61. 	cin >> m;
  62. 	for(int i = 1, l, r; i <= m; i++){
  63. 		cin >> l >> r;
  64. 		query x;
  65. 		x.l = l;
  66. 		x.r = r;
  67. 		x.id = i;
  68. 		q.pb(x);
  69. 	}
  70. 	sort(q.begin(), q.end(), cmpmo);
  71. //	for(query x : q){
  72. //		cout << x.l << " " << x.r << " " << x.id << "\n";
  73. //	}
  74. 	bool st = 1;
  75. 	int cl, cr;
  76. 	for(query x : q){
  77. 		if(st){
  78. 			cl = x.l;
  79. 			cr = x.r;
  80. 			for(int i = cl; i <= cr; i++){
  81. 				add(i);
  82. 			}
  83. 		}
  84. 		else{
  85. 			while(cl > x.l){
  86. 				cl--;
  87. 				add(cl);
  88. 			}
  89. 			while(cr < x.r){
  90. 				cr++;
  91. 				add(cr);
  92. 			}
  93. 			while(cl < x.l){
  94. 				remove(cl);
  95. 				cl++;
  96. 			}
  97. 			while(cr > x.r){
  98. 				remove(cr);
  99. 				cr--;
  100. 			}
  101. 		}
  102. 		st = 0;
  103. 		for(int i = 0; i <= B; i++){
  104.             if(block[i]){
  105.                 for(int j = i*B + 1; j <= (i+1)*B; j++){
  106.                     if(cnt[j]==1){
  107.                         res[x.id] = j;
  108. 						break;
  109.                     }
  110.                 }
  111.                 break;
  112.             }
  113.         }
  114. 	}
  115. 	for(int i=1; i<=m; i++){
  116. 		cout << res[i] << "\n";
  117. 	}
  118. }
  119.  
  120. signed main(){
  121. //	freopen("*.INP", "r", stdin);
  122. //    freopen("*.OUT", "w", stdout);
  123.     ios::sync_with_stdio(0);
  124.     cin.tie(0); cout.tie(0);
  125.     int tt = 1; //cin >> tt;
  126.     while(tt--){
  127.     	solve();
  128. 	}
  129. }
  130.  
  131. /*
  132. sample
  133.  
  134.  
  135.  
  136. */
  137.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/aJCb1i
language:
C++14 (gcc 8.3)
created:
10 days 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!