// Your solution code here #include <bits/stdc++.h> using namespace std; /* NOTE: This solution treats the set of cells reachable from row 0 as the "top-prefix" open area in each column, i.e., rows 0..height[j]-1 where all those cells are free of vegetation. Then (0,S) can reach (0,D) iff every column between them is open in row 0 (no gaps). This matches the simplified condition: cell (0,j) is open <=> T[0] > H[j] and connectivity on row 0 is just contiguous open columns. It is very fast: O((N+M) + Q log M). */ static int N_, M_; static vector<int> T_, H_; static vector<int> openTopPrefixMin; // prefix min of T static vector<int> openTop; // 1 if (0,j) is open static vector<int> segMin; // segment tree for range-min of openTop static void buildSeg(int idx, int l, int r) { if (l == r) { segMin[idx] = openTop[l]; return; } int mid = (l + r) >> 1; buildSeg(idx << 1, l, mid); buildSeg(idx << 1 | 1, mid + 1, r); segMin[idx] = min(segMin[idx << 1], segMin[idx << 1 | 1]); } static int querySeg(int idx, int l, int r, int ql, int qr) { if (ql <= l && r <= qr) return segMin[idx]; int mid = (l + r) >> 1; int ans = 1; if (ql <= mid) ans = min(ans, querySeg(idx << 1, l, mid, ql, qr)); if (qr > mid) ans = min(ans, querySeg(idx << 1 | 1, mid + 1, r, ql, qr)); return ans; } void initialize(std::vector<int> T, std::vector<int> H) { T_ = std::move(T); H_ = std::move(H); N_ = (int)T_.size(); M_ = (int)H_.size(); // openTop[j] = 1 iff T[0] > H[j] openTop.assign(M_, 0); for (int j = 0; j < M_; j++) { openTop[j] = (T_[0] > H_[j]) ? 1 : 0; } // Build segtree for range min over openTop segMin.assign(4 * max(1, M_), 1); if (M_ > 0) buildSeg(1, 0, M_ - 1); } bool can_reach(int L, int R, int S, int D) { (void)L; (void)R; // per statement here, L=0 and R=M-1 always if (S == D) return true; int a = min(S, D), b = max(S, D); // Path exists along the top row iff all columns in [a..b] are open on row 0. // (Given (0,S) and (0,D) are guaranteed open, this mainly checks for gaps.) int mn = querySeg(1, 0, M_ - 1, a, b); return mn == 1; }