fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MAX = 1e5 + 5;
  6.  
  7.  
  8. int n, q;
  9. pair<int, int> a[MAX];
  10. int u[MAX], v[MAX], k[MAX];
  11. int l[MAX], r[MAX];
  12. int bit[MAX];
  13.  
  14. void update(int idx, int val) {
  15.     for (; idx <= n; idx += idx & -idx) bit[idx] += val;
  16. }
  17.  
  18. int query_bit(int idx) {
  19.     int sum = 0;
  20.     for (; idx > 0; idx -= idx & -idx) sum += bit[idx];
  21.     return sum;
  22. }
  23.  
  24. int get(int l, int r) {
  25.     return query_bit(r) - query_bit(l - 1);
  26. }
  27.  
  28. int main() {
  29.     ios_base::sync_with_stdio(false);
  30.     cin.tie(NULL);
  31.  
  32.     cin >> n >> q;
  33.  
  34.     for (int i = 1; i <= n; i++) {
  35.         cin >> a[i].first;
  36.         a[i].second = i;
  37.     }
  38.     sort(a + 1, a + n + 1);
  39.  
  40.     for (int i = 1; i <= q; i++) {
  41.         cin >> u[i] >> v[i] >> k[i];
  42.         l[i] = 1; r[i] = n;
  43.     }
  44.  
  45.     for (int t = 0; t < 20; t++) {
  46.         vector<pair<int, int>> b;
  47.         for (int i = 1; i <= q; i++) {
  48.             if (l[i] < r[i]) {
  49.                 b.push_back({(l[i] + r[i]) / 2, i});
  50.             }
  51.         }
  52.  
  53.         if (b.empty()) break;
  54.  
  55.         sort(b.begin(), b.end());
  56.  
  57.         memset(bit, 0, sizeof bit);
  58.  
  59.         int j = 0, sz = b.size();
  60.  
  61.         for (int i = 1; i <= n; i++) {
  62.             while (j < sz && b[j].first < i) {
  63.                 int id = b[j].second;
  64.                 if (get(u[id], v[id]) >= k[id])
  65.                     r[id] = b[j].first;
  66.                 else l[id] = b[j].first + 1;
  67.                 j++;
  68.             }
  69.             update(a[i].second, 1);
  70.         }
  71.  
  72.         while (j < sz) {
  73.             int id = b[j].second;
  74.             if (get(u[id], v[id]) >= k[id])
  75.                 r[id] = b[j].first;
  76.             else l[id] = b[j].first + 1;
  77.             j++;
  78.         }
  79.     }
  80.  
  81.     for (int i = 1; i <= q; i++) {
  82.         cout << a[l[i]].first << "\n";
  83.     }
  84.  
  85.     return 0;
  86. }
  87.  
Success #stdin #stdout 0s 6084KB
comments (?)
stdin
copy 
5 3
3 7 2 1 8
1 3 1
1 5 3
2 4 3
stdout
copy 
2
3
7
https://ideone.com/dgUUUs
language:
C++14 (gcc 8.3)
created:
7 hours 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!