#include <vector> #include <algorithm> #include <iostream> #include <numeric> using namespace std; // Disjoint Set Union (DSU) structure struct DSU { vector<int> parent; DSU(int n) { parent.resize(n); iota(parent.begin(), parent.end(), 0); } int find(int i) { if (parent[i] == i) return i; return parent[i] = find(parent[i]); } void unite(int i, int j) { int root_i = find(i); int root_j = find(j); if (root_i != root_j) { parent[root_i] = root_j; } } }; static DSU* dsu_ptr = nullptr; void initialize(std::vector<int> T, std::vector<int> H) { int N = T.size(); int M = H.size(); // 1. Precompute Prefix Min and Max for T // PMin[k] = min(T[0]...T[k]) // PMax[k] = max(T[0]...T[k]) vector<int> PMin(N), PMax(N); PMin[0] = T[0]; PMax[0] = T[0]; for (int i = 1; i < N; i++) { PMin[i] = min(PMin[i - 1], T[i]); PMax[i] = max(PMax[i - 1], T[i]); } // 2. Compute BaseMaxT for each column // BaseMaxT[j] = max T reachable from (0, j) moving only vertically vector<int> BaseMaxT(M); // PMin is non-increasing. We can use binary search (upper_bound logic) // to find the largest k such that PMin[k] > H[j]. // Since PMin is descending, we can use std::upper_bound with a custom comparator // or just checking rbegin. simpler to write manual binary search or just use existing structure. // PMin: [10, 8, 5, 2]. We want last index where val > H[j]. for (int j = 0; j < M; j++) { int h = H[j]; if (T[0] <= h) { BaseMaxT[j] = -1; // Cannot even exist at (0, j) continue; } // Binary search for the deepest reachable row int low = 0, high = N - 1; int deepest = 0; while (low <= high) { int mid = low + (high - low) / 2; if (PMin[mid] > h) { deepest = mid; low = mid + 1; } else { high = mid - 1; } } BaseMaxT[j] = PMax[deepest]; } // 3. Propagate Reachability vector<int> Reach(M); // Left to Right int current_cap = -1; for (int j = 0; j < M; j++) { if (current_cap > H[j]) { // Can enter from left current_cap = max(current_cap, BaseMaxT[j]); } else { // Cannot enter from left, reset to base current_cap = BaseMaxT[j]; } Reach[j] = current_cap; } // Right to Left current_cap = -1; for (int j = M - 1; j >= 0; j--) { if (current_cap > H[j]) { current_cap = max(current_cap, BaseMaxT[j]); } else { current_cap = BaseMaxT[j]; } Reach[j] = max(Reach[j], current_cap); } // 4. Build DSU if (dsu_ptr) delete dsu_ptr; dsu_ptr = new DSU(M); for (int j = 0; j < M - 1; j++) { // We can move between j and j+1 if the Reachability at j is enough to cross H[j+1] // OR if Reachability at j+1 is enough to cross H[j]. if (Reach[j] > H[j+1] || Reach[j+1] > H[j]) { dsu_ptr->unite(j, j + 1); } } } bool can_reach(int L, int R, int S, int D) { // For L=0, R=M-1 subtask, we ignore L and R. return dsu_ptr->find(S) == dsu_ptr->find(D); }