fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAX = 1e5 + 5;
  5.  
  6. int N, M, A[MAX], back[MAX];
  7. vector<int> s[MAX * 4], v[MAX * 4], arr;
  8. map<int, int> MAP;
  9.  
  10. void build(int low, int high, int node){
  11. 	int parent = node >> 1;
  12. 	for(auto it:s[parent]){
  13. 		if(it >= low and it <= high) s[node].push_back(it);
  14. 	}
  15.  
  16. 	if(low == high) return;
  17.  
  18. 	int mid = (low + high) >> 1;
  19.  
  20. 	if(s[node].size()){
  21. 		if(s[node][0] > mid) v[node].push_back(0);
  22. 		else v[node].push_back(1);
  23. 		for(int i=1; i<s[node].size(); ++i){
  24. 			if(s[node][i] > mid) v[node].push_back(v[node].back());
  25. 			else v[node].push_back(v[node].back() + 1);			
  26. 		}
  27. 	}
  28. 	else return;
  29.  
  30. 	build(low, mid, node << 1);
  31. 	build(mid + 1, high, 1 | node << 1);
  32. }
  33.  
  34. int query(int low, int high, int node, int l, int r, int rank){
  35.  
  36. 	if(low == high) return low;
  37.  
  38. 	int mid = (low + high) >> 1, new_l = 0, new_r = 0, to_l = 0, to_r = 0;
  39.  
  40. 	to_l = v[node][r];
  41. 	if(l) to_l = to_l - v[node][l - 1];
  42.  
  43. 	to_r = r - l + 1 - to_l;
  44.  
  45. 	if(to_l >= rank){
  46. 		if(l) new_l = v[node][l - 1];
  47. 		new_r = new_l + to_l - 1;
  48. 		return query(low, mid, node << 1, new_l, new_r, rank);
  49. 	}
  50. 	else{
  51. 		if(l) new_l = l - v[node][l - 1];
  52. 		new_r = new_l + to_r - 1;
  53. 		return query(mid + 1, high, 1 | node << 1, new_l, new_r, rank - to_l);
  54. 	}
  55. }
  56.  
  57. void compress(){
  58. 	for(int i=1; i<=N; ++i) arr.push_back(A[i]);
  59. 	sort(arr.begin(), arr.end());
  60. 	int c = 0;
  61. 	for(auto it:arr){
  62. 		if(MAP.find(it) == MAP.end()) MAP[it] = ++c;
  63. 	}
  64. 	for(int i=1; i<=N; ++i){
  65. 		int v = MAP[A[i]];
  66. 		back[v] = A[i];
  67. 		A[i] = v;
  68. 	}
  69. }
  70.  
  71. int main() {
  72. 	ios_base::sync_with_stdio(false);
  73.  
  74. 	cin >> N >> M;
  75. 	for(int i=1; i<=N; ++i) cin >> A[i];
  76.  
  77. 	compress();
  78.  
  79. 	int mid = (1 + MAX) >> 1;
  80.  
  81. 	for(int i=1; i<=N; ++i) s[1].push_back(A[i]);
  82.  
  83. 	if(s[1][0] > mid) v[1].push_back(0);
  84. 	else v[1].push_back(1);
  85.  
  86. 	for(int i=1; i<N; ++i){
  87. 		if(s[1][i] > mid) v[1].push_back(v[1].back());
  88. 		else v[1].push_back(v[1].back() + 1);
  89. 	}
  90.  
  91. 	build(1, mid, 2);
  92. 	build(mid + 1, MAX, 3);
  93.  
  94. 	while(M--){
  95. 		int L, R, K; cin >> L >> R >> K;
  96. 		--L; --R;
  97. 		cout << back[query(1, MAX, 1, L, R, K)] << endl;
  98. 	}
  99.  
  100. 	return 0;
  101. }
Success #stdin #stdout 0s 34768KB
comments (?)
stdin
copy 
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
stdout
copy 
5
6
3
https://ideone.com/ZyZS6R
language:
C++14 (gcc 8.3)
created:
6 years 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!