fork download
copy 
  1. /*
  2.     author  : [ Godsent ]
  3.     created : 2025.08.13 17:30:25
  4. */
  5.  
  6. #include <bits/stdc++.h>
  7. #include <ext/pb_ds/assoc_container.hpp>
  8. #include <ext/pb_ds/tree_policy.hpp>
  9. #define el "\n"
  10. #define int long long
  11. #define lb lower_bound
  12. #define ub upper_bound
  13. #define fi first
  14. #define se second
  15. #define sz(x) ((int)(x).size())
  16. #define all(v) (v).begin(), (v).end()
  17. #define pb push_back
  18. #define prs(n) fixed << setprecision(n)
  19.  
  20. const int mod = 1e9 + 7;
  21. const int N = 2e5 + 5;
  22. const int INF = 1e18;
  23.  
  24. using namespace std;
  25. using namespace __gnu_pbds;
  26. template <typename T>
  27. using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  28.  
  29. int n, q;
  30. vector<pair<int,int>> b;
  31. int a[N], bit[N], res[N];
  32.  
  33. void update(int i) {
  34.   while(i <= n) {
  35.     bit[i] += 1;
  36.     i += i & -1;
  37.   }
  38. }
  39.  
  40. int get(int i) {
  41.   int res = 0;
  42.   while (i > 0) {
  43.     res += bit[i];
  44.     i -= i & -i;  
  45.   }
  46.   return res;
  47. }
  48.  
  49. signed main() {
  50.   ios_base::sync_with_stdio(false);
  51.   cin.tie(0);
  52.   cout.tie(0);
  53.  
  54. #ifndef ONLINE_JUDGE
  55.   freopen("test.in", "r", stdin);
  56.   freopen("test.out", "w", stdout);
  57. #endif
  58.  
  59.   cin >> n >> q;
  60.   int l = INF, r = -INF;
  61.   for (int i = 1; i <= n; i++) {
  62.     cin >> a[i];
  63.     b.pb({a[i], i});
  64.     l = min(l, a[i]);
  65.     r = max(r, a[i]);
  66.   }
  67.  
  68.   sort(all(b));
  69.  
  70.   vector<vector<int>> bucket(q, vector<int>(7));
  71.   for (int i = 0; i < q; i++) {
  72.     int u, v, k;
  73.     cin >> u >> v >> k;
  74.     bucket[i][0] = (l + r) >> 1;
  75.     bucket[i][1] = l;
  76.     bucket[i][2] = r;
  77.     bucket[i][3] = u;
  78.     bucket[i][4] = v;
  79.     bucket[i][5] = k;
  80.     bucket[i][6] = i + 1;
  81.   }
  82.  
  83.   bool done = false;
  84.   while(!done) {
  85.     done = true;
  86.  
  87.     sort(all(bucket));
  88.  
  89.     int idx = 0;
  90.     for (int i = 0; i < q; i++) {
  91.       if (bucket[i][1] > bucket[i][2]) continue;
  92.       if (bucket[i][1] <= bucket[i][2]) done = false;
  93.       while (b[idx].fi <= bucket[i][0]) {
  94.         update(b[idx].se);
  95.         idx++;
  96.       }
  97.       int s = get(bucket[i][4]) - get(bucket[i][3] - 1);
  98.       if (s >= bucket[i][5]) {
  99.         res[bucket[i][6]] = bucket[i][0];
  100.         bucket[i][2] = bucket[i][0] - 1;
  101.       }
  102.       else bucket[i][1] = bucket[i][0] + 1;
  103.     }
  104.     for (int i = 1; i <= n; i++) bit[i] = 0;
  105.   }
  106.  
  107.   for (int i = 1; i <= q; i++) cout << res[i] << el;
  108.  
  109.   return 0;
  110. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/WXBPd7
language:
C++14 (gcc 8.3)
created:
23 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!