fork download
copy 
  1. #include <bits/stdc++.h> 
  2. using namespace std; 
  3.  
  4. const int N=1e5+2; 
  5.  
  6. vector<int> seg[N]; 
  7. pair<int, int> B[N]; 
  8. int arr[N];
  9.  
  10. void build(int ci, int st, int end, pair<int, int>* B) 
  11. { 
  12. 	if (st == end) { 
  13. 		seg[ci].push_back(B[st].second); 
  14. 		return; 
  15. 	} 
  16. 	int mid = (st + end) / 2; 
  17. 	build(2 * ci + 1, st, mid, B); 
  18. 	build(2 * ci + 2, mid + 1, end, B); 
  19. 	merge(seg[2 * ci + 1].begin(), seg[2 * ci + 1].end(), seg[2 * ci + 2].begin(), seg[2 * ci + 2].end(), back_inserter(seg[ci])); 
  20. } 
  21. int query(int ci, int st, int end, int l, int r, int k) 
  22. { 
  23. 	if (st == end) 
  24. 		return seg[ci][0]; 
  25. 	int p = upper_bound(seg[2 * ci + 1].begin(), seg[2 * ci + 1].end(), r) - lower_bound(seg[2 * ci + 1].begin(), seg[2 * ci + 1].end(), l); 
  26.  
  27. 	int mid = (st + end) / 2; 
  28. 	if (p >= k) 
  29. 		return query(2 * ci + 1, st, mid, l, r, k); 
  30. 	else
  31. 		return query(2 * ci + 2, mid + 1, end, l, r, k - p); 
  32. } 
  33. int main() 
  34. { 
  35. 	int n,m;
  36. 	cin>>n>>m;
  37. 	for(int i=0;i<n;i++){
  38. 		cin>>arr[i];
  39. 	}
  40. 	for (int i = 0; i < n; i++) { 
  41. 		B[i] = { arr[i], i }; 
  42. 	} 
  43. 	sort(B, B + n); 
  44. 	build(0, 0, n - 1, B); 
  45.  
  46. 	int l,r,x;
  47.  
  48. 	for(int i=0;i<m;i++){
  49. 		cin>>l>>r>>x;
  50. 		cout<<arr[query(0,0,n-1,l-1,r-1,x)]<<endl;
  51. 	}
  52. 	return 0;
  53. } 
  54.  
Success #stdin #stdout 0s 5952KB
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/NrP7OO
language:
C++14 (gcc 8.3)
created:
3 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!