// Solution for the "Llama Path" problem. // The grid is defined by row temperatures T[i] and column humidities H[j]. // A cell (i,j) is free iff T[i] > H[j]. // For each query we need to decide whether (0,S) can reach (0,D) staying // inside free cells. Both S and D are guaranteed to be free at row 0. #include <bits/stdc++.h> using namespace std; // --------------------------------------------------------------------- // Global data filled by `initialize` and used by `can_reach` // --------------------------------------------------------------------- static vector<int> T_glob; // temperatures of rows static vector<int> H_glob; // humidities of columns static int maxReachableTemp; // maximum temperature among rows // that are reachable from row 0 static struct SegTree { int n = 0; vector<int> seg; // iterative segment tree for range max void init(const vector<int>& a) { n = (int)a.size(); seg.assign(2 * n, INT_MIN); for (int i = 0; i < n; ++i) seg[n + i] = a[i]; for (int i = n - 1; i > 0; --i) seg[i] = max(seg[i << 1], seg[i << 1 | 1]); } // inclusive query on [l, r] int query(int l, int r) const { int res = INT_MIN; for (l += n, r += n; l <= r; l >>= 1, r >>= 1) { if (l & 1) res = max(res, seg[l++]); if (!(r & 1)) res = max(res, seg[r--]); } return res; } } Hseg; // --------------------------------------------------------------------- // Initialization: runs once per test case // --------------------------------------------------------------------- void initialize(vector<int> T, vector<int> H) { T_glob = std::move(T); H_glob = std::move(H); int N = (int)T_glob.size(); int M = (int)H_glob.size(); // Minimum humidity over all columns. int Hmin = *min_element(H_glob.begin(), H_glob.end()); // Find the first row (index > 0) that has no free cell at all. // A row i is completely blocked iff T[i] <= Hmin. int firstDead = N; // N means "no dead row" maxReachableTemp = T_glob[0]; // start with row 0 for (int i = 1; i < N; ++i) { if (T_glob[i] <= Hmin) { // this row cannot be entered firstDead = i; break; } if (T_glob[i] > maxReachableTemp) maxReachableTemp = T_glob[i]; } // If there is no dead row, the loop visited all rows and maxReachableTemp // already equals the global maximum temperature. // Build a segment tree on the humidity array for range‑maximum queries. Hseg.init(H_glob); } // --------------------------------------------------------------------- // Query: is there a valid path from (0,S) to (0,D) staying inside columns [L,R]? // In the problem L = 0 and R = M‑1, so we only need to look at the columns // between S and D. // --------------------------------------------------------------------- bool can_reach(int L, int R, int S, int D) { // The interval we must cross on the top row. int left = min(S, D); int right = max(S, D); // Maximum humidity among the columns we must cross. int maxH = Hseg.query(left, right); // Reachable iff every column in the interval has humidity < maxReachableTemp. // Columns with humidity >= maxReachableTemp are completely blocked in the // reachable part of the grid (they have no free cell in any row we can ever // reach from the top). return maxH < maxReachableTemp; }