fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct Query {
  6.     int l, r;  // [l, r)
  7.     int val, count_le;
  8.  
  9.     int ans_range_l, ans_range_r;
  10.  
  11.     int ans_mid() const {
  12.         return ans_range_l + (ans_range_r - ans_range_l) / 2;
  13.     }
  14. };
  15.  
  16. const int maxn = 100010;
  17. const int maxq = 5050;
  18. const int inf = (int)1e9 + 100;
  19. int n, q;
  20. pair<int, int> a[maxn];
  21. Query qr[maxq];
  22.  
  23. vector<int> val_it[maxn * 2];
  24.  
  25. int main() {
  26. #ifdef LOCAL
  27.     freopen("main.inp", "r", stdin);
  28.     freopen("main.out", "w", stdout);
  29. #endif
  30.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  31.     cin >> n >> q;
  32.     for (int i = 0; i < n; ++i) {
  33.         cin >> a[i].first;
  34.         a[i].second = i;
  35.     }
  36.  
  37.     for (int i = 0; i < q; ++i) {
  38.         cin >> qr[i].l >> qr[i].r >> qr[i].val;
  39.         --qr[i].l;
  40.         qr[i].ans_range_l = -inf;
  41.         qr[i].ans_range_r = inf;
  42.     }
  43.  
  44.     sort(a, a + n);
  45.  
  46.     for (int i = 0; i < n; ++i) {
  47.         for (int p = a[i].second + n; p > 0; p >>= 1)
  48.             val_it[p].push_back(a[i].first);
  49.     }
  50.  
  51.     while (true) {
  52.         vector<Query*> temp_qr;
  53.         for (int i = 0; i < q; ++i) {
  54.             if (qr[i].ans_range_l == qr[i].ans_range_r) continue;
  55.             qr[i].count_le = 0;
  56.             temp_qr.push_back(qr + i);
  57.         }
  58.         if (temp_qr.empty()) break;
  59.  
  60.         sort(temp_qr.begin(), temp_qr.end(), [](const Query* u, const Query* v) {
  61.             return u->ans_mid() < v->ans_mid();
  62.         });
  63.  
  64.         vector<vector<Query*>> qr_it(2 * n);
  65.         for (auto cur_qr: temp_qr) {
  66.             for (int l = cur_qr->l + n, r = cur_qr->r + n; l < r; l >>= 1, r >>= 1) {
  67.                 if (l & 1) qr_it[l++].push_back(cur_qr);
  68.                 if (r & 1) qr_it[--r].push_back(cur_qr);
  69.             }
  70.         }
  71.  
  72.         for (int root = 1; root < 2 * n; ++root) {
  73.             auto& vi = val_it[root];
  74.             auto& qi = qr_it[root];
  75.             if (vi.empty() or qi.empty()) continue;
  76.             int ptr_v = 0;
  77.             for (auto cur_qr: qi) {
  78.                 while (ptr_v < (int)vi.size() and vi[ptr_v] <= cur_qr->ans_mid()) ++ ptr_v;
  79.                 cur_qr->count_le += ptr_v;
  80.             }
  81.         }
  82.  
  83.         for (int i = 0; i < q; ++i) {
  84.             if (qr[i].ans_range_l == qr[i].ans_range_r) continue;
  85.             if (qr[i].count_le >= qr[i].val) {
  86.                 qr[i].ans_range_r = qr[i].ans_mid();
  87.             } else {
  88.                 qr[i].ans_range_l = qr[i].ans_mid() + 1;
  89.             }
  90.         }
  91.     }
  92.  
  93.     for (int i = 0; i < q; ++i) cout << qr[i].ans_range_l << '\n';
  94.  
  95.     return 0;
  96. }
  97.  
Success #stdin #stdout 0s 8336KB
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/tgiUz8
language:
C++ (gcc 8.3)
created:
4 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!