// Your solution code here #include <bits/stdc++.h> using namespace std; // ---------- DSU ---------- struct DSU { vector<int> p, r; DSU() {} DSU(int n) { init(n); } void init(int n) { p.resize(n); r.assign(n, 0); iota(p.begin(), p.end(), 0); } int find(int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; } void unite(int a, int b) { a = find(a); b = find(b); if (a == b) return; if (r[a] < r[b]) swap(a, b); p[b] = a; if (r[a] == r[b]) r[a]++; } }; // ---------- Fenwick (BIT) for counts + kth ---------- struct BIT { int n; vector<int> bit; // 1-based BIT() : n(0) {} BIT(int n_) { init(n_); } void init(int n_) { n = n_; bit.assign(n + 1, 0); } void add(int idx, int delta) { for (int i = idx + 1; i <= n; i += i & -i) bit[i] += delta; } int sumPrefix(int idx) const { // sum [0..idx], idx<0 => 0 if (idx < 0) return 0; int s = 0; for (int i = idx + 1; i > 0; i -= i & -i) s += bit[i]; return s; } // smallest pos such that prefix sum >= k (k is 1-based). returns 0-based pos. int find_kth(int k) const { int idx = 0; int bitmask = 1 << (31 - __builtin_clz(n)); // highest power of 2 <= n while (bitmask) { int nxt = idx + bitmask; if (nxt <= n && bit[nxt] < k) { idx = nxt; k -= bit[nxt]; } bitmask >>= 1; } return idx; // 0-based position } }; // ---------- Globals filled by initialize ---------- static DSU g_dsu; static int gM = 0; // segment tree for range max on H struct SegMax { int n; // original size int size; // power-of-two vector<int> seg; void build(const vector<int>& a) { n = (int)a.size(); size = 1; while (size < n) size <<= 1; seg.assign(2 * size, INT_MIN); for (int i = 0; i < n; i++) seg[size + i] = a[i]; for (int i = size - 1; i >= 1; i--) seg[i] = max(seg[2 * i], seg[2 * i + 1]); } int range_max(int l, int r) const { // inclusive if (l > r) return INT_MIN; l += size; r += size; int res = INT_MIN; while (l <= r) { if (l & 1) res = max(res, seg[l++]); if (!(r & 1)) res = max(res, seg[r--]); l >>= 1; r >>= 1; } return res; } }; static SegMax g_seg; // ---------- Core algorithm ---------- void initialize(std::vector<int> T, std::vector<int> H) { int N = (int)T.size(); int M = (int)H.size(); gM = M; // prefix minima of temperatures vector<int> pref_min(N); int cur_min = T[0]; for (int i = 0; i < N; i++) { cur_min = min(cur_min, T[i]); pref_min[i] = cur_min; } // depth[col] = largest row i such that min(T[0..i]) > H[col] vector<int> depth(M, -1); for (int j = 0; j < M; j++) { int h = H[j]; int lo = 0, hi = N - 1, ans = -1; while (lo <= hi) { int mid = (lo + hi) >> 1; if (pref_min[mid] > h) { ans = mid; lo = mid + 1; } else { hi = mid - 1; } } depth[j] = ans; } // bucket columns by exact depth vector<vector<int>> cols_by_depth(N); for (int j = 0; j < M; j++) { int d = depth[j]; if (d >= 0) cols_by_depth[d].push_back(j); } // segment tree for max(H) queries g_seg.build(H); // DSU over columns g_dsu.init(M); // BIT: active columns are those with depth >= current row i BIT bit(M); // Process rows from bottom to top; when at row i, activate columns with depth == i. for (int i = N - 1; i >= 0; i--) { for (int col : cols_by_depth[i]) { bit.add(col, 1); // ----- nearest active on the left ----- int cnt_left = bit.sumPrefix(col - 1); if (cnt_left > 0) { int left = bit.find_kth(cnt_left); // rightmost active < col if (left + 1 <= col - 1) { if (g_seg.range_max(left + 1, col - 1) < T[i]) { g_dsu.unite(left, col); } } else { g_dsu.unite(left, col); } } // ----- nearest active on the right ----- int total_active = bit.sumPrefix(M - 1); int cnt_up_to_col = bit.sumPrefix(col); // includes col if (total_active > cnt_up_to_col) { int right = bit.find_kth(cnt_up_to_col + 1); // leftmost active > col if (col + 1 <= right - 1) { if (g_seg.range_max(col + 1, right - 1) < T[i]) { g_dsu.unite(col, right); } } else { g_dsu.unite(col, right); } } } } } bool can_reach(int /*L*/, int /*R*/, int S, int D) { // L=0 and R=M-1 always in this version. return g_dsu.find(S) == g_dsu.find(D); }