fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int M=4e5+4;
  4. int n,q,a[M];
  5. vector<int>tree[M],v;
  6. #define all(v) v.begin(),v.end()
  7. void build(int l,int r,int id)
  8. {
  9. 	if(l==r)
  10. 	{
  11. 		tree[id].push_back(a[l]);
  12. 		return;
  13. 	}
  14. 	int m=(l+r)>>1;
  15. 	build(l,m,2*id);
  16. 	build(m+1,r,2*id+1);
  17. 	merge(all(tree[2*id]),all(tree[2*id+1]),back_inserter(tree[id]));
  18. }
  19. int query(int l,int r,int id,int ql,int qr,int val)
  20. {
  21. 	if(r<ql || qr<l || ql>qr) return 0;
  22. 	if(ql<=l && r<=qr) 
  23. 	return (int)(upper_bound(all(tree[id]),val-1)-tree[id].begin());
  24. 	int m=(l+r)>>1;
  25. 	return query(l,m,2*id,ql,qr,val)+query(m+1,r,2*id+1,ql,qr,val);
  26. }
  27. int main()
  28. {
  29. 	scanf("%d%d",&n,&q);
  30. 	for(int i=1;i<=n;i++)
  31. 	{
  32. 		scanf("%d",&a[i]);
  33. 		v.push_back(a[i]);
  34. 	}
  35. 	sort(all(v));
  36. 	for(int i=1;i<=n;i++) a[i]=lower_bound(all(v),a[i])-v.begin()+1;
  37. 	build(1,n,1);
  38. 	while(q--)
  39. 	{
  40. 		int l,r,k;
  41. 		scanf("%d%d%d",&l,&r,&k);
  42. 		int lo=1,hi=n,ans=-1;
  43. 		while(lo<=hi)
  44. 		{
  45. 			int md=(lo+hi)>>1;
  46. 			int vv=query(1,n,1,l,r,md);
  47. 			if(k>vv) lo=md+1;
  48. 			else  if(k<vv) hi=md-1;
  49. 			else
  50. 			{
  51. 				ans=md;
  52. 				break;
  53. 			}
  54. 		}
  55. 		printf("%d\n",v[ans-1]);
  56. 	}
  57. 	return 0;
  58. }
Success #stdin #stdout 0s 26176KB
comments (?)
stdin
copy 
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
stdout
copy 
6
7
4
https://ideone.com/PCX6n1
language:
C++14 (gcc 8.3)
created:
5 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!