Advertisement
mzh_pb

Untitled

Dec 10th, 2023
700
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.42 KB | Source Code | 0 0
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3.  
  4. #define int int64_t
  5.  
  6. #define rng(i, a, b) for (int i = a; i < b; i++)
  7. #define rep(i, b) rng(i, 0, b)
  8. #define gnr(i, a, b) for (int i = b - 1; i >= a; i--)
  9. #define per(i, b) gnr(i, 0, b)
  10.  
  11. #define all(x) begin(x), end(x)
  12. #define sz(x) int(size(x))
  13.  
  14. #define pb push_back
  15. #define eb emplace_back
  16. #define lb lower_bound
  17. #define ub upper_bound
  18.  
  19. #define f first
  20. #define s second
  21.  
  22. using namespace std;
  23. using namespace __gnu_pbds;
  24.  
  25. struct Segment {
  26.     int len;
  27.     int pref, suff, mx;
  28.  
  29.     Segment operator+(Segment b) {
  30.         Segment ret;
  31.         ret.len = len + b.len;
  32.         ret.pref = pref + (pref == len ? b.pref : 0);
  33.         ret.suff = (b.suff == b.len ? suff : 0) + b.suff;
  34.         ret.mx = max({mx, b.mx, suff + b.pref});
  35.         return ret;
  36.     }
  37. };
  38.  
  39. int tree_sz;
  40. vector<Segment> segtree;
  41.  
  42. void update(int i, bool v, int x = 0, int tl = 0, int tr = tree_sz) {
  43.     if (tl + 1 == tr) {
  44.         segtree[x] = {1, v, v, v};
  45.         return;
  46.     }
  47.     int mid = (tl + tr) / 2;
  48.     if (i < mid) {
  49.         update(i, v, 2 * x + 1, tl, mid);
  50.     } else {
  51.         update(i, v, 2 * x + 2, mid, tr);
  52.     }
  53.     segtree[x] = segtree[2 * x + 1] + segtree[2 * x + 2];
  54. }
  55.  
  56. void solve() {
  57.     int n, b;
  58.     cin >> n >> b;
  59.  
  60.     vector<int> f(n);
  61.     rep(i, n) {
  62.         cin >> f[i];
  63.     }
  64.  
  65.     vector<array<int, 3>> queries(b);
  66.     rep(i, b) {
  67.         cin >> queries[i][0] >> queries[i][1];
  68.         queries[i][2] = i;
  69.     }
  70.     sort(all(queries));
  71.  
  72.     vector<int> to_rem(n);
  73.     iota(all(to_rem), 0);
  74.     sort(all(to_rem), [&](int a, int b) {
  75.         return f[a] > f[b];
  76.     });
  77.  
  78.     tree_sz = 1;
  79.     while (tree_sz < n) {
  80.         tree_sz *= 2;
  81.     }
  82.     segtree.resize(2 * tree_sz, {});
  83.     rep(i, n) {
  84.         update(i, 1);
  85.     }
  86.  
  87.     vector<bool> ans(b);
  88.     for (auto [mx_d, step, idx] : queries) {
  89.         while (!to_rem.empty() && f[to_rem.back()] <= mx_d) {
  90.             update(to_rem.back(), 0);
  91.             to_rem.pop_back();
  92.         }
  93.         ans[idx] = segtree[0].mx < step;
  94.     }
  95.     rep(i, b) {
  96.         cout << ans[i] << '\n';
  97.     }
  98. }
  99.  
  100. int32_t main() {
  101. #ifndef LOCAL
  102.     freopen("snowboots.in", "r", stdin);
  103.     freopen("snowboots.out", "w", stdout);
  104. #endif
  105.     ios::sync_with_stdio(false);
  106.     cin.tie(nullptr);
  107.  
  108.     int tc = 1;
  109.     // cin >> tc;
  110.     while (tc--) {
  111.         solve();
  112.     }
  113.  
  114.     return 0;
  115. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement