fork download
copy 
  1. //Pranet Verma
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. typedef struct Node* pnode;
  6. struct Node {
  7.     int cnt;
  8.     pnode l, r;
  9. };
  10. pnode getIdentity() {
  11.     pnode ret = new Node();
  12.     ret->l = ret->r = ret;
  13.     ret->cnt = 0;
  14.     return ret;
  15. }
  16. pnode null = getIdentity();
  17.  
  18. int query(pnode v, pnode u, int k, int l, int r) {
  19.     while (l != r) {
  20.         int m = (l + r) / 2;
  21.         int inLeft = v->l->cnt - u->l->cnt;
  22.         if (inLeft >= k) {
  23.             v = v->l;
  24.             u = u->l;
  25.             r = m;
  26.         } else {
  27.             v = v->r;
  28.             u = u->r;
  29.             k = k - inLeft;
  30.             l = m + 1; 
  31.         }
  32.     } 
  33.     return l;
  34. }
  35.  
  36. pnode insert(pnode root, int x, int l, int r) {
  37.     pnode u = new Node{root->cnt + 1, root->l, root->r};
  38.     pnode ret = u;
  39.     while (l != r) {
  40.         int m = (l + r) / 2;
  41.         if (x <= m) {
  42.             u->l = new Node{root->l->cnt + 1, root->l, root->r};
  43.             u->r = root->r;
  44.             r = m;
  45.             root = root->l;
  46.             u = u->l;
  47.         } else {
  48.             u->l = root->l;
  49.             u->r = new Node{root->r->cnt + 1, root->l, root->r};
  50.             l = m + 1;
  51.             root = root->r;
  52.             u = u->r;
  53.         }
  54.     }
  55.     return ret;
  56. }
  57.  
  58. const int MAXN = 100005;
  59. int a[MAXN], b[MAXN];
  60. pnode root[MAXN] = {null};
  61. int main() {
  62.     int n, m;
  63.     scanf("%d %d", &n, &m);
  64.     for (int i = 0; i < n; ++i) {
  65.         scanf("%d", &a[i]);
  66.     } 
  67.     memcpy(b, a, sizeof(b));
  68.     sort(b, b + n);
  69.     for (int i = 1; i <= n; ++i) {
  70.         int compressedValue = lower_bound(b, b + n, a[i - 1]) - b;
  71.         root[i] = insert(root[i - 1], compressedValue, 0, n - 1);
  72.     }
  73.     for (int i = 0; i < m; ++i) {
  74.         int l, r, k;
  75.         scanf("%d %d %d", &l, &r, &k);
  76.         int compressedValue = query(root[r], root[l - 1], k, 0, n - 1);
  77.         printf("%d\n", b[compressedValue]);
  78.     }
  79. }
Success #stdin #stdout 0s 17624KB
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/jfwdZh
language:
C++14 (gcc 8.3)
created:
6 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!