fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define maxn 100100
  6. #define gc getchar_unlocked
  7.  
  8. void scanint(int &x)
  9. {
  10.     register int c = gc();
  11.     x = 0;
  12.     bool neg=false;
  13.     if(c=='-')
  14.         neg=true;
  15.     for(;(c<48 || c>57);c = gc());
  16.     for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
  17.     if(neg)
  18.         x=-x;
  19. }
  20.  
  21. struct node{
  22.     int cnt;
  23.     node *left;
  24.     node *right;
  25.     node(){
  26.         this->cnt=0;
  27.         this->left=this;
  28.         this->right=this;
  29.     }
  30.     node(int cnt, node *left, node *right):cnt(cnt), left(left), right(right){}
  31.     node *insert(int L, int R, int val);
  32. };
  33.  
  34. node *null;
  35. node *tree[maxn];
  36.  
  37. node *node::insert(int L, int R, int val)
  38. {
  39.     if(L==R)
  40.         return new node(this->cnt+1, null, null); //insert no. in node
  41.     else{
  42.         int mid = (L+R)>>1;
  43.         if(val<=mid) //val lies in left child, update left
  44.             return new node(this->cnt+1, this->left->insert(L, mid, val), this->right);
  45.         else // val lies in right child, update right
  46.             return new node(this->cnt+1, this->left, this->right->insert(mid+1, R, val));
  47.     }
  48. }
  49.  
  50. int getkth(node *low, node *high, int L, int R, int val)
  51. {
  52.     if(L==R)
  53.         return L;
  54.     int lsum = high->left->cnt - low->left->cnt;
  55.     int mid = (L+R)>>1;
  56.     if(lsum>=val)
  57.         return getkth(low->left, high->left, L, mid, val);
  58.     else
  59.         return (getkth(low->right, high->right, mid+1, R, val-lsum));
  60. }
  61.  
  62. int main()
  63. {
  64.     int n, m, i, l, r, k;
  65.     scanint(n);
  66.     scanint(m);
  67.     int arr[n];
  68.     map<int, int> m1;
  69.     for(i=0; i<n; i++){
  70.         scanint(arr[i]);
  71.         m1[arr[i]];
  72.     }
  73.     map<int, int>::iterator it;
  74.     int ind=0;
  75.     int sor[n];
  76.     for(it=m1.begin(); it!=m1.end(); ++it){
  77.         m1[it->first] = ind;
  78.         sor[ind] = it->first;
  79.         ind++;
  80.     }
  81.     tree[0] = new node();
  82.     for(i=1; i<=n; i++)
  83.         tree[i] = tree[i-1]->insert(0, ind, m1[arr[i-1]]);
  84.     while(m--){
  85.         scanint(l);
  86.         scanint(r);
  87.         scanint(k);
  88.         int ans = sor[getkth(tree[l-1], tree[r], 0, ind, k)];
  89.         printf("%d\n", ans);
  90.     }
  91.     return 0;
  92. }
  93.  
Success #stdin #stdout 0s 3668KB
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/SQYW60
language:
C++ (gcc 8.3)
created:
9 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!