PXGuX0 - Online C++0x Compiler & Debugging Tool

/*
    author  : [ Godsent ]
    created : 2025.08.16 15:39:24
*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define el "\n"
#define int long long
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define prs(n) fixed << setprecision(n)

const int mod = 1e9 + 7;
const int N = 1e5 + 5;
const int INF = 1e18;

using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int n, q;
int a[N], bit[N], res[N];
pair<int,int> b[N];

void update(int i) {
  while(i <= n) {
    bit[i] += 1;
    i += i & -i;
  }
}

int get(int i) {
  int res = 0;
  while(i > 0) {
    res += bit[i];
    i -= i & -i;
  }
  return res;
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

#ifndef ONLINE_JUDGE
  freopen("test.in", "r", stdin);
  freopen("test.out", "w", stdout);
#endif

  cin >> n >> q;
  int l = INT_MAX, r = INT_MIN;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    l = min(l, a[i]);
    r = max(r, a[i]);
    b[i] = {a[i], i};
  }

  sort(b + 1, b + 1 + n);

  vector<vector<int>> bucket(q, vector<int>(7));
  for (int i = 0; i < q; i++) {
    int u, v, k;
    cin >> u >> v >> k;
    bucket[i][1] = l;
    bucket[i][2] = r;
    bucket[i][3] = u;
    bucket[i][4] = v;
    bucket[i][5] = k;
    bucket[i][6] = i + 1;
  }

  bool done = false;
  while(!done) {
    done = true;

    for (int i = 0; i < q; i++) {
      if (bucket[i][1] <= bucket[i][2]) {
        done = false;
        int mid = (bucket[i][1] + bucket[i][2]) >> 1;
        bucket[i][0] = mid;
      }
    }

    if (done) break;

    sort(all(bucket));

    int idx = 1;
    for (int i = 0; i < q; i++) {
      if (bucket[i][1] > bucket[i][2]) continue;
      while(idx <= n && bucket[i][0] >= b[idx].fi) {
        update(b[idx].se);
        idx++;
      }
      int s = get(bucket[i][4]) - get(bucket[i][3] - 1);
      if (s >= bucket[i][5]) {
        res[bucket[i][6]] = bucket[i][0];
        bucket[i][2] = bucket[i][0] - 1;
      }
      else bucket[i][1] = bucket[i][0] + 1;
    }
    fill(bit + 1, bit + 1 + n, 0);
  }

  for (int i = 1; i <= q; i++) cout << res[i] << el;

  return 0;
}