fork download 
  1. #include <bits/stdc++.h>
  2. #define up(i,a,b) for (int i = (int)a; i <= (int)b; i++)
  3. #define ep emplace_back
  4. #define all(x) x.begin(), x.end()
  5. using namespace std;
  6.  
  7. const int maxn = 1e5 + 10;
  8. const int LOG = log2(maxn)+2;
  9. int a[maxn];
  10. struct PST_node{
  11.     int l,r,sum;
  12. };
  13. PST_node T[maxn*LOG];
  14. int cnt = 0;
  15. int n,q;
  16.  
  17.  
  18. int ROOT[maxn];
  19.  
  20. void push_up(int nod){
  21.     T[nod].sum = T[T[nod].l].sum + T[T[nod].r].sum;
  22. }
  23.  
  24. void update(int& nod, int prev_nod, int l, int r, int& pos, int val){
  25.     nod = ++cnt;
  26.     T[nod] = T[prev_nod];
  27.     if (l == r){
  28.         T[nod].sum += val;
  29.         return;
  30.     }
  31.     int mid = (l+r) >> 1;
  32.     if (pos <= mid) update(T[nod].l, T[prev_nod].l, l, mid, pos, val);
  33.     else update(T[nod].r, T[prev_nod].r, mid+1, r, pos, val);
  34.     push_up(nod);
  35. }
  36.  
  37. int query(int& nod, int& prev_nod, int l, int r, int k){
  38.     if (l == r) return l;
  39.     int mid = (l+r) >> 1;
  40.     int CNT = T[T[nod].l].sum - T[T[prev_nod].l].sum;
  41.     if (CNT >= k) return query(T[nod].l, T[prev_nod].l, l, mid, k);
  42.     return query(T[nod].r, T[prev_nod].r, mid+1, r, k - CNT);
  43. }
  44.  
  45. vector<int> V;
  46.  
  47. signed main(){
  48.     ios_base::sync_with_stdio(false);
  49.     cin.tie(0);
  50.     #define Task "A"
  51.     if (fopen(Task".inp", "r")){
  52.         freopen(Task".inp", "r", stdin);
  53.         freopen(Task".out", "w", stdout);
  54.     }
  55.  
  56.     cin >> n >> q;
  57.     up(i,1,n){
  58.         cin >> a[i];
  59.         V.push_back(a[i]);
  60.     }
  61.     sort(all(V));
  62.     V.resize(unique(all(V)) - V.begin());
  63.     up(i,1,n) {
  64.         int x = lower_bound(all(V), a[i]) - V.begin() + 1;
  65.         update(ROOT[i], ROOT[i-1], 1, n, x, 1);
  66.     }
  67.  
  68.     V.clear();
  69.     V.push_back(-1e9 - 7);
  70.     up(i,1,n) V.push_back(a[i]);
  71.     sort(all(V));
  72.     V.resize(unique(all(V)) - V.begin());
  73.  
  74.     up(i,1,q){
  75.         int l,r,k;
  76.         cin >> l >> r >> k;
  77.         int x = query(ROOT[r], ROOT[l-1], 1, n, k);
  78.         cout << V[x] << "\n";
  79.     }
  80. }
  81.  
Success #stdin #stdout 0.01s 5524KB
comments (?)
stdin 
5 5
8 2 4 4 6 
1 5 5
1 3 2
4 4 1
2 3 2
5 5 1
stdout 
8
4
4
4
6
https://ideone.com/Sv6HSs
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!