fork(21) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAX = 100005;
  5. const int LIM = 263005;
  6.  
  7. #define inchar          getchar_unlocked
  8. #define outchar(x)      putchar_unlocked(x)
  9.  
  10. template<typename T> void inpos(T &x){x=0;register T c=inchar();while(((c<48)||(c>57))&&(c!='-'))c=inchar();bool neg=false;if(c=='-')neg=true;for(;c<48||c>57;c=inchar());for(;c>47&&c<58;c=inchar())x=(x<<3)+(x<<1)+(c&15);if(neg)x=-x;}
  11. template<typename T> void outpos(T n){if(n<0){outchar('-');n*=-1;}char snum[65];int i=0;do {snum[i++]=n%10+'0';n/=10;}while(n);i=i-1;while(i>=0)outchar(snum[i--]);outchar('\n');}
  12.  
  13. int inp[MAX];
  14. vector< pair<int,int> > nums;
  15. vector<int> seg[LIM];
  16.  
  17. void build_merge_sort(int t, int i, int j) {
  18. 	if (i==j) {
  19. 		seg[t].push_back(nums[i].second);
  20. 		return ;
  21. 	}
  22. 	int left = t<<1, right = left|1, mid = (i+j)/2;
  23. 	build_merge_sort(left, i, mid);
  24. 	build_merge_sort(right, mid+1, j);
  25. 	merge(seg[left].begin(), seg[left].end(), seg[right].begin(), seg[right].end(), back_inserter(seg[t]));
  26. }
  27.  
  28. int query_kth(int t, int i, int j, int l, int r, int k) {
  29. 	if (i == j) {
  30. 		return seg[t][0];
  31. 	}
  32. 	int left = t<<1, right = left|1, mid = (i+j)/2, total;
  33. 	auto it = upper_bound(seg[left].begin(), seg[left].end(), r);
  34. 	total = it - lower_bound(seg[left].begin(), seg[left].end(), l);
  35. 	if (total >= k) {
  36. 		return query_kth(left, i, mid, l, r, k);
  37. 	}
  38. 	else {
  39. 		return query_kth(right, mid+1, j, l, r, k-total);
  40. 	}
  41. }
  42.  
  43. int main() {
  44. 	int n, m, x, y, k, idx, ans;
  45. 	inpos(n), inpos(m);
  46. 	for(int i=0; i<n; ++i) {
  47. 		inpos(x);
  48. 		inp[i] = x;
  49. 		nums.push_back(make_pair(x, i));
  50. 	}
  51. 	sort(nums.begin(), nums.end());
  52. 	build_merge_sort(1, 0, n-1);
  53. 	while (m--) {
  54. 		inpos(x), inpos(y), inpos(k);
  55. 		--x; --y;
  56. 		idx = query_kth(1, 0, n-1, x, y, k);
  57. 		ans = inp[idx];
  58. 		outpos(ans);
  59. 	}
  60. 	return 0;
  61. }
Success #stdin #stdout 0s 21784KB
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/T4gxB9
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!