fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define fst first
  6. #define snd second
  7. #define all(c) ((c).begin()), ((c).end())
  8. #define endl '\n'
  9.  
  10. const int INF = 1 << 30;
  11. const int MAXN = 1e5+5;
  12. const int MAXH = 18;
  13. const int MAXUPD = 1e5+5;
  14.  
  15. typedef int ll;//long long
  16.  
  17. struct Node {
  18.   ll value;
  19.   Node* left;
  20.   Node* right;
  21.  
  22.   Node() : value(0), left(nullptr), right(nullptr) {}
  23.   void *operator new(size_t size);
  24. };
  25.  
  26. Node buffer[2*MAXN+MAXH*MAXUPD];
  27. void * Node::operator new(size_t size) {
  28.   static int ptr = 0;
  29.   return &buffer[ptr++];
  30. }
  31.  
  32. ll aggregate_function(ll left, ll right){
  33.   return left + right;
  34. }
  35.  
  36. Node* build(vector<ll> &arr, int l, int r){
  37.   Node* node = new Node();
  38.   if(l == r) {
  39.     node->value = arr[l];
  40.     return node;
  41.   }
  42.  
  43.   int m = (l + r) / 2;
  44.   node->left = build(arr, l, m);
  45.   node->right = build(arr, m+1, r);
  46.   node->value = aggregate_function(node->left->value, node->right->value);
  47.   return node;
  48. }
  49.  
  50. ll query(Node* root, int start, int end, int rootStart, int rootEnd) {
  51.   if(start > end) return 0;
  52.   if(rootStart == start && rootEnd == end)
  53.     return root->value;
  54.  
  55.   int m = (rootStart+rootEnd)/2;
  56.   ll ans = aggregate_function(
  57.   	query(root->left,start,min(m,end), rootStart, m),
  58.   	query(root->right,max(m+1,start),end, m+1, rootEnd));
  59.   return ans;
  60. }
  61.  
  62. Node* update(Node* root, int pos, ll value, int rootStart, int rootEnd) {
  63.   Node* node = new Node();
  64.   if(rootStart == rootEnd) {
  65.     node->value = value;
  66.     return node;
  67.   }
  68.   int m = (rootStart + rootEnd) / 2;
  69.   if(pos <= m) {
  70.     node->left = update(root->left, pos, value, rootStart, m);
  71.     node->right = root->right;
  72.   } else {
  73.     node->right = update(root->right, pos, value, m+1, rootEnd);
  74.     node->left = root->left;
  75.   }
  76.   node->value = aggregate_function(node->left->value, node->right->value);
  77.   return node;
  78. }
  79.  
  80. void solve() {
  81.   int n,m; 
  82.   cin >> n >> m;
  83.   vector<ll> org(n+1);
  84.   vector<pair<ll,ll>> aux(n+1, {-INF,-INF});
  85.   vector<ll> compress(n+1,0);
  86.   vector<Node*> versions(n+1);
  87.   versions[0] = build(compress, 0, n);
  88.  
  89.   for(int i = 1; i <= n; i++) {
  90.     cin >> org[i];
  91.     aux[i].fst = org[i];
  92.     aux[i].snd = i;
  93.   }
  94.  
  95.   sort(all(aux));
  96.  
  97.   vector<ll> backToNormal(n+1,0);
  98.   for(int i = 1; i <= n; i++) {
  99.     compress[aux[i].snd] = i;
  100.     backToNormal[i] = aux[i].fst;
  101.   }
  102.   // for(int i = 1; i <= n; i++) {
  103.   //   cout << compress[i] << " ";
  104.   // }
  105.   // cout << endl;
  106.  
  107.  
  108.   for(int i = 1; i <= n; i++) {
  109.     versions[i] = update(versions[i-1], compress[i], 1, 0, n);
  110.   }
  111.  
  112.   while(m--) {
  113.     ll i,j,k;
  114.     cin >> i >> j >> k;
  115.     ll l = 1;
  116.     ll r = n;
  117.     ll ans = -1;
  118.     Node* L = versions[i-1];
  119.     Node* R = versions[j];
  120.     int cur = k;
  121.     int curStart = 0, curEnd = n;
  122.     while(curStart!=curEnd) {
  123.       int cnt = R->left->value - L->left->value;
  124.       int mid = (curStart+curEnd)/2;
  125.       if(cnt >= cur){
  126.       	L = L->left;
  127.       	R = R->left;
  128.       	curEnd = mid;
  129.       }else{
  130.       	L = L->right;
  131.       	R = R->right;
  132.       	cur -= cnt;
  133.       	curStart = mid+1;
  134.       }
  135.     }
  136.     cout << backToNormal[curStart] << endl;
  137.   }
  138. }
  139.  
  140. int main() {
  141.   ios::sync_with_stdio(false);
  142.   cin.tie(nullptr);
  143.   int t = 1;
  144.   //cin >> t;
  145.   while(t--)
  146.     solve();
  147. }
  148.  
Success #stdin #stdout 0.01s 50460KB
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/VF2331
language:
C++14 (gcc 8.3)
created:
281 days 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!