fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. #define MOD 1000000007
  4. #define MODSET(d) if ((d) >= MOD) d %= MOD;
  5. #define MODADDSET(d) if ((d) >= MOD) d -= MOD;
  6.  
  7. using namespace std;
  8.  
  9. #define MAXN 100000
  10. #define LOGN 16
  11.  
  12. struct node
  13. {
  14. 	node *left, *right;
  15. 	int value;
  16.  
  17. 	node(int v, node *l, node *r)
  18. 	{
  19. 		this->value = v;
  20. 		this->left = l;
  21. 		this->right = r;
  22. 	}
  23.  
  24. 	node* insert(int l, int r, int index);
  25. };
  26.  
  27. node* null;
  28.  
  29. node* node::insert(int l, int r, int index)
  30. {
  31. 	if (l <= index && index <= r)
  32. 	{
  33. 		if (l == r)
  34. 		{
  35. 			return new node(1, null, null);
  36. 		}
  37. 		else
  38. 		{
  39. 			int mid = (l + r)/2;
  40. 			return new node(value+1, this->left->insert(l, mid, index), this->right->insert(mid+1, r, index));
  41. 		}
  42. 	}
  43. 	else
  44. 	{
  45. 		return this;
  46. 	}
  47. }
  48.  
  49. node* root[MAXN+5];
  50.  
  51. int query(node* root, int l, int r, int k)
  52. {
  53. 	if (l == r)
  54. 	{
  55. 		return l;
  56. 	}
  57.  
  58. 	int count = root->left->value;
  59. 	int mid = (l + r)/2;
  60.  
  61. 	if (count >= k)
  62. 	{
  63. 		return query(root->left, l, mid, k);
  64. 	}
  65. 	else
  66. 	{
  67. 		return query(root->right, mid+1, r, k - count);
  68. 	}
  69. }
  70.  
  71. vector<int> positions[MAXN+5];
  72. int arr[MAXN+5];
  73.  
  74. int main()
  75. {
  76.     #ifdef VSP4
  77.         freopen("input.txt", "r", stdin);
  78.         freopen("output.txt", "w", stdout);
  79.     #endif
  80.  
  81.     int n, q, i, j, d, L, K;
  82.  
  83.     null = new node(0, NULL, NULL);
  84.     null->left = null->right = null;
  85.  
  86.     scanf("%d %d", &n, &q);
  87.  
  88.     for (i = 1; i <= n; i++)
  89.     {
  90. 		scanf("%d", &d);
  91. 		arr[i] = d;
  92. 		positions[d].push_back(i);
  93. 	}
  94.  
  95. 	root[MAXN+1] = null;
  96.  
  97. 	for (i = MAXN; i >= 1; i--)
  98. 	{
  99. 		root[i] = root[i+1];
  100. 		if (!positions[i].empty())
  101. 		{
  102. 			for (auto p: positions[i])
  103. 			{
  104. 				root[i] = root[i]->insert(1, MAXN, p);
  105. 			}
  106. 		}
  107. 	}
  108.  
  109. 	while (q--)
  110. 	{
  111. 		scanf("%d %d", &L, &K);
  112. 		printf("%d\n", arr[query(root[L], 1, MAXN, K)]);
  113. 	}
  114.  
  115.     return 0;
  116. }
  117.  
Success #stdin #stdout 0s 5368KB
comments (?)
stdin
copy 
10 4
1 9 2 8 3 7 4 6 5 10
4 4
3 2
1 6
8 1
stdout
copy 
4
8
7
9
https://ideone.com/uThUxc
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!