fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MX = 3e5 + 5;
  5. const int N = 1e5 + 5;
  6. typedef pair<int,int> pii;
  7. typedef pair<pii,int> piii;
  8. #define f first
  9. #define s second
  10. int SZ, cnt[N], Arr[MX], mx = 0, mn;
  11. pii Ans[MX], tree[4 * N];
  12. piii query[MX];
  13.  
  14. bool cmp(piii x, piii y){
  15. 	int _x = x.f.f/SZ, _y = y.f.f/SZ;
  16. 	if(_x != _y) return _x < _y;
  17. 	return x.f.s < y.f.s;
  18. }
  19.  
  20. void build(int node, int st, int en){
  21. 	if(st == en){
  22. 		tree[node].f = tree[node].s = 0;
  23. 		return;
  24. 	}
  25.  
  26. 	int l = 2 * node, r = l + 1, mid = (st + en)/2;
  27. 	build(l, st, mid);
  28. 	build(r, mid + 1, en);
  29. 	tree[node].f = tree[node].s = 0;
  30. }
  31.  
  32. void update(int node, int st, int en, int id, int val){
  33. 	if(st >= id && en <= id){
  34. 		tree[node] = pii(cnt[val], val);
  35. 		return;
  36. 	}
  37.  
  38. 	if(en < id || st > id) return;
  39.  
  40. 	int l = 2 * node, r = l + 1, mid = (st + en)/2;
  41.     update(l, st, mid, id, val);
  42.     update(r, mid + 1, en, id, val);
  43.  
  44.     if(tree[l].f > tree[r].f) { tree[node].f = tree[l].f; tree[node].s = tree[l].s; }
  45.     else { tree[node].f = tree[r].f; tree[node].s = tree[r].s; }
  46. }
  47.  
  48. void add(int num){
  49. 	cnt[num]++;
  50. 	update(1, mn, mx, num, num);
  51. }
  52.  
  53. void _remove(int num){
  54. 	cnt[num]--;
  55. 	update(1, mn, mx, num, num);
  56. }
  57.  
  58. int main() {
  59. 	int n, q, c, fir, sec;
  60. 	scanf("%d %d", &n, &c); mx = 0; mn = N;
  61. 	SZ = sqrt(n);
  62. 	for(int i = 0; i < n; scanf("%d", &Arr[i]), mx = max(mx, Arr[i]), mn = min(mn, Arr[i]), i++);
  63.  
  64. 	scanf("%d", &q);
  65. 	for(int i = 0; i < q; i++){
  66. 		scanf("%d %d", &fir, &sec);
  67. 		query[i].f.f = --fir;
  68. 		query[i].f.s = --sec;
  69. 		query[i].s = i;
  70. 	}
  71. 	sort(query, query + q, cmp);
  72. 	memset(cnt, 0, sizeof(cnt));
  73. 	build(1, mn, mx);
  74.  
  75. 	int left = 0, right = -1;
  76. 	for(int i = 0; i < q; i++){
  77. 		int l = query[i].f.f, r = query[i].f.s, id = query[i].s;
  78.  
  79. 		while(right < r){
  80. 			right++;
  81. 			add(Arr[right]);
  82. 		}
  83.  
  84. 		while(right > r){
  85. 			_remove(Arr[right]);
  86. 			right--;
  87. 		}
  88.  
  89. 		while(left < l){
  90. 			_remove(Arr[left]);
  91. 			left++;
  92. 		}
  93.  
  94. 		while(left > l){
  95. 			left--;
  96. 			add(Arr[left]);
  97. 		}
  98.  
  99. 		int val = (r - l + 1)/2;
  100. 		pii p = tree[1];
  101. 		if(p.f <= val) Ans[id] = pii(0,0);
  102. 		else Ans[id] = pii(1,p.s);
  103. 	}
  104.  
  105. 	for(int i = 0; i < q; i++){
  106. 		pii p = Ans[i];
  107. 		if(p.f == 0) printf("no\n");
  108. 		else printf("yes %d\n", p.s);
  109. 	}
  110. 	return 0;
  111. }
Success #stdin #stdout 0s 14024KB
comments (?)
stdin
copy 
10 3
1 2 1 2 1 2 3 2 3 3
8
1 2
1 3
1 4
1 5
2 5
2 6
6 9
7 10
stdout
copy 
no
yes 1
no
yes 1
no
yes 2
no
yes 3
https://ideone.com/NqSI3j
language:
C++14 (gcc 8.3)
created:
7 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!