fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define sz(o) ((int)o.size())
  5. #define all(o) o.begin(), o.end()
  6. #define rep(i, a, b) for(int i = (a); i <= (b); i++)
  7. #define repr(i, a, b) for(int i = (a); i >= (b); i--)
  8.  
  9. typedef long long int ll;
  10. typedef vector<ll> vll;
  11. typedef vector<int> vi;
  12.  
  13. void fs(int &nn) {
  14.     bool neg = false;
  15.     register int ch;
  16.     nn = 0;
  17.     ch = getchar();
  18.     if (ch == '-') {
  19.         neg = true;
  20.         ch = getchar();
  21.     }
  22.     for (; (ch > 47 && ch < 58); ch = getchar()) nn = nn * 10 + ch - 48;
  23.     if (neg) nn *= -1;
  24. }
  25.  
  26. const int maxn = 111111;
  27. int n, m, maxi;
  28. int a[maxn], rm[maxn];
  29. map<int, int> M;
  30.  
  31. struct node {
  32.     int count;
  33.     node *left, *right;
  34.     node(int count, node *left, node *right) :count(count), left(left), right(right) {}
  35. };
  36.  
  37. node *root[maxn];
  38. node *null = new node(0, NULL, NULL);
  39.  
  40. node* build(node *cur, int l, int r, int c) {
  41.     if (l == r) return new node(cur->count + 1, null, null);
  42.     else {
  43.         int mid = (l + r) >> 1;
  44.         node *newNode = new node(0, null, null);
  45.         if (c <= mid) {
  46.             newNode->right = cur->right;
  47.             newNode->left = build(cur->left, l, mid, c);
  48.             newNode->count = newNode->left->count + newNode->right->count;
  49.         }
  50.         else {
  51.             newNode->left = cur->left;
  52.             newNode->right = build(cur->right, mid + 1, r, c);
  53.             newNode->count = newNode->left->count + newNode->right->count;
  54.         }
  55.         return newNode;
  56.     }
  57. }
  58.  
  59. int query(node *a, node *b, int l, int r, int k) {
  60.     if (l == r) return l;
  61.     else {
  62.         int mid = (l + r) >> 1;
  63.         int count = a->left->count - b->left->count;
  64.         if (count >= k) return query(a->left, b->left, l, mid, k);
  65.         return query(a->right, b->right, mid + 1, r, k - count);
  66.     }
  67. }
  68.  
  69. void solve() {
  70.     fs(n);
  71.     fs(m);
  72.     rep(i, 1, n){
  73.         fs(a[i]);
  74.         M[a[i]];
  75.     }
  76.     maxi = 0;
  77.     for(auto it = M.begin(); it != M.end(); it++){
  78.         M[it->first] = ++maxi;
  79.         rm[maxi] = it->first;
  80.     }
  81.  
  82.     null->left = null->right = null;
  83.     root[0] = null;
  84.     rep(i, 1, n) root[i] = build(root[i - 1], 1, maxi, M[a[i]]);
  85.  
  86.     while(m--){
  87.         int l, r, k;
  88.         fs(l);
  89.         fs(r);
  90.         fs(k);
  91.         printf("%d\n", rm[query(root[r], root[l - 1], 1, maxi, k)]);
  92.     }
  93. }
  94.  
  95. int main() {
  96.     #ifndef ONLINE_JUDGE
  97.     freopen("in.txt", "r", stdin);
  98.     freopen("out.txt", "w", stdout);
  99.     #endif
  100.     /*ios_base::sync_with_stdio(false);
  101.     cin.tie(NULL);
  102.     cout.tie(NULL);*/
  103.     cout << setprecision(10);
  104.     clock_t b = clock();
  105.     solve();
  106.     clock_t e = clock();
  107.     cerr << (double(e - b) / CLOCKS_PER_SEC) << " sec";
  108.     return 0;
  109. }
Success #stdin #stdout #stderr 0s 4520KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
1.7e-05 sec
https://ideone.com/EkAOzu
language:
C++14 (gcc 8.3)
created:
6 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!