fork(2) download
copy 
  1. // taken the idea of self pointer to avoid handling null pointer from coach fegla
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5. const int MAX = 4e6;
  6. struct node{
  7.     node* l,* r;
  8.     int sz;
  9.     node(){
  10.       l = r = this;
  11.       sz = 0;
  12.     }
  13.     static node* empty;
  14.  
  15. };
  16. node nodes[MAX];
  17. int nxt = 0;
  18. node* node::empty = &nodes[0];
  19. node* newNode(int sz = 0,node* l = node::empty,node* r = node::empty){
  20.     nxt++;
  21.     node *ret = &nodes[nxt];
  22.     ret->sz = sz;
  23.     ret->l = l;
  24.     ret->r = r;
  25.     return ret;
  26. }
  27. node* insert(node* prev,int val,int tl = -1e9,int tr = 1e9){
  28.     if(val > tr || val < tl)return prev;
  29.     if(tl == tr)return newNode(prev->sz+1);
  30.     int mid = tl+(tr-tl)/2;
  31.     node* l = insert(prev->l,val,tl,mid);
  32.     node* r = insert(prev->r,val,mid+1,tr);
  33.     return newNode(l->sz+r->sz,l,r);
  34. }
  35. int query(node* st,node* en,int k,int tl = -1e9,int tr = 1e9){
  36.     if(tl == tr)return tl;
  37.     int mid = tl+(tr-tl)/2;
  38.     int lsz = en->l->sz - st->l->sz;
  39.     if(k <= lsz)return query(st->l,en->l,k,tl,mid);
  40.     else        return query(st->r,en->r,k-lsz,mid+1,tr);
  41. }
  42. const int N = 1e5+5;
  43. node* roots[N];
  44. int main(){
  45.     roots[0] = newNode();
  46.     int n,m;
  47.     scanf("%d%d",&n,&m);
  48.     for (int i = 1;i <= n; ++i){
  49.         int x;
  50.         scanf("%d",&x);
  51.         roots[i] = insert(roots[i-1],x);
  52.     }
  53.     for (int i = 0;i < m; ++i){
  54.         int l,r,k;
  55.         scanf("%d%d%d",&l,&r,&k);
  56.         printf("%d\n",query(roots[l-1],roots[r],k));
  57.     }
  58.  
  59.     return 0;
  60. }
  61.  
Runtime error #stdin #stdout 0.15s 50680KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/lbUOfb
language:
C++14 (gcc 8.3)
created:
8 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!