fork(8) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef int64_t   ll;
  7. typedef pair<int,int> ii;
  8.  
  9. #define EL printf("\n")
  10. #define pb push_back
  11. #define mp make_pair
  12. #define X  first
  13. #define Y  second
  14.  
  15. typedef vector<int> data;
  16.  
  17. const int   N = 100100;
  18. int         n, q, a[N], L, R, k, res, cnt, f;
  19. data        t[4*N], nil;
  20.  
  21. data combine(data u, data v)
  22. {
  23.     data ans = nil;
  24.     int i = 0, j = 0;
  25.     while (i < u.size() and j < v.size()) {
  26.         if (u[i] < v[j]) ans.pb(u[i++]);
  27.         else ans.pb(v[j++]);
  28.     }
  29.     while (i < u.size()) ans.pb(u[i++]);
  30.     while (j < v.size()) ans.pb(v[j++]);
  31.     return ans;
  32. }
  33.  
  34. void build(int k, int l, int r)
  35. {
  36.     if (l == r) {
  37.         t[k].pb(a[l]);
  38.         return ;
  39.     }
  40.     int mid = (l+r)/2;
  41.     build(k*2, l, mid);
  42.     build(k*2+1, mid+1, r);
  43.     t[k] = combine(t[k*2], t[k*2+1]);
  44. }
  45.  
  46. void get(int node, int l, int r)
  47. {
  48.     if (r < L or R < l) return ;
  49.     if (L <= l and r <= R) {
  50.         int i = 0, j = t[node].size()-1, pos = -1;
  51.         while (i <= j) {
  52.             int mid = (i+j)/2;
  53.             if (t[node][mid] <= res) {
  54.                 pos = mid;
  55.                 i = mid+1;
  56.             }
  57.             else j = mid-1;
  58.         }
  59.         if (pos == -1) return ;
  60.         if (t[node][pos] == res) f = true;
  61.         cnt += pos + 1;
  62.         if (t[node][pos] == res) cnt--;
  63.         return ;
  64.     }
  65.     int mid = (l+r)/2;
  66.     get(node*2,l,mid);
  67.     get(node*2+1,mid+1,r);
  68. }
  69.  
  70. int main()
  71. {
  72.     //freopen("INP.INP","r",stdin);
  73.     //freopen("OUT.OUT","w",stdout);
  74.  
  75.     scanf("%d", &n);
  76.     for (int i=1;i<=n;i++) scanf("%d", &a[i]);
  77.  
  78.     build(1,1,n);
  79.  
  80.     scanf("%d", &q);
  81.     while (q--) {
  82.         scanf("%d%d%d", &L,&R,&k);
  83.         int l = 0, r = t[1].size()-1;
  84.         while (l <= r) {
  85.             int mid = (l+r)/2;
  86.             res = t[1][mid];
  87.             cnt = 0;
  88.             f = 0;
  89.             get(1,1,n);
  90.             if (cnt == k-1 and f) {
  91.                 printf("%d\n", res);
  92.                 break;
  93.             }
  94.             if (cnt < k) l = mid+1; else r = mid-1;
  95.         }
  96.     }
  97.  
  98.     return 0;
  99. }
  100.  
Runtime error #stdin #stdout 0s 16288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/GTScHq
language:
C++ (gcc 8.3)
created:
9 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!