# Untitled

Dec 10th, 2023
700
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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. }