// Your solution code here #include <bits/stdc++.h> using namespace std; /* IOI 2025 "Obstacles for a Llama" – specialized variant where L=0, R=M-1 always. We preprocess the unique connected component (in the whole grid of free cells) that each top-row column belongs to, then each query is O(1). Key ingredients (adapted from known solution ideas for this task): - nearest strictly smaller humidity on left/right (lf, rg) - range maximum query on H to test whether a whole horizontal interval can be crossed - bestTemp(h): maximum temperature reachable by going down using a column of humidity h (i.e., among rows r such that min_{0..r} T > h) */ static int N_, M_; static vector<int> T_, H_; static vector<int> prefMinT_; // prefMinT_[i] = min(T[0..i]) (non-increasing) static vector<int> prefMaxT_; // prefMaxT_[i] = max(T[0..i]) (non-decreasing) static vector<int> lg2_; static vector<vector<int>> stMaxH_; // sparse table for max on H static vector<int> lf_, rg_; // nearest strictly smaller humidity indices static vector<int> minVal_; // minVal_[j] = minimal humidity value reachable from column j (top row) static vector<int> compL_, compR_; // final component interval [L,R] under threshold bestTemp(minVal) static inline int rangeMaxH(int l, int r) { if (l > r) std::swap(l, r); int len = r - l + 1; int k = lg2_[len]; return max(stMaxH_[k][l], stMaxH_[k][r - (1 << k) + 1]); } // bestTemp(h): max temperature T[x] among rows x where prefMinT_[x] > h. // If no such row exists, return -1. static inline int bestTemp(int h) { int lo = 0, hi = N_ - 1, ans = -1; while (lo <= hi) { int mid = (lo + hi) >> 1; if (prefMinT_[mid] > h) { ans = mid; lo = mid + 1; } else { hi = mid - 1; } } return (ans == -1 ? -1 : prefMaxT_[ans]); } static inline int leftBoundary(int pos, int t) { // smallest L in [0..pos] such that max(H[L..pos]) < t int lo = 0, hi = pos, ans = pos; while (lo <= hi) { int mid = (lo + hi) >> 1; if (rangeMaxH(mid, pos) < t) { ans = mid; hi = mid - 1; } else { lo = mid + 1; } } return ans; } static inline int rightBoundary(int pos, int t) { // largest R in [pos..M-1] such that max(H[pos..R]) < t int lo = pos, hi = M_ - 1, ans = pos; while (lo <= hi) { int mid = (lo + hi) >> 1; if (rangeMaxH(pos, mid) < t) { ans = mid; lo = mid + 1; } else { hi = mid - 1; } } 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(); // prefix min/max on T prefMinT_.assign(N_, 0); prefMaxT_.assign(N_, 0); { int mn = INT_MAX, mx = INT_MIN; for (int i = 0; i < N_; i++) { mn = min(mn, T_[i]); mx = max(mx, T_[i]); prefMinT_[i] = mn; prefMaxT_[i] = mx; } } // sparse table for max on H lg2_.assign(M_ + 1, 0); for (int i = 2; i <= M_; i++) lg2_[i] = lg2_[i >> 1] + 1; int K = lg2_[M_] + 1; stMaxH_.assign(K, vector<int>(M_, 0)); stMaxH_[0] = H_; for (int k = 1; k < K; k++) { int half = 1 << (k - 1); int span = 1 << k; for (int i = 0; i + span <= M_; i++) { stMaxH_[k][i] = max(stMaxH_[k - 1][i], stMaxH_[k - 1][i + half]); } } // nearest strictly smaller on left (lf_) lf_.assign(M_, -1); { vector<int> st; st.reserve(M_); for (int i = 0; i < M_; i++) { while (!st.empty() && H_[st.back()] >= H_[i]) st.pop_back(); lf_[i] = st.empty() ? -1 : st.back(); st.push_back(i); } } // nearest strictly smaller on right (rg_) rg_.assign(M_, -1); { vector<int> st; st.reserve(M_); for (int i = M_ - 1; i >= 0; i--) { while (!st.empty() && H_[st.back()] >= H_[i]) st.pop_back(); rg_[i] = st.empty() ? -1 : st.back(); st.push_back(i); } } // Compute minVal_ in increasing order of humidity: // minVal[u] = min(H[u], minVal[v]) for v in {lf[u],rg[u]} that are "jumpable" from u. // Jump condition from u to v: // bestTemp(H[u]) > max(H[min(u,v)..max(u,v)]). minVal_.assign(M_, 0); vector<int> ord(M_); iota(ord.begin(), ord.end(), 0); stable_sort(ord.begin(), ord.end(), [&](int a, int b) { if (H_[a] != H_[b]) return H_[a] < H_[b]; return a < b; }); for (int u : ord) { int t = bestTemp(H_[u]); int best = H_[u]; if (t != -1) { int v = lf_[u]; if (v != -1 && t > rangeMaxH(u, v)) best = min(best, minVal_[v]); v = rg_[u]; if (v != -1 && t > rangeMaxH(u, v)) best = min(best, minVal_[v]); } minVal_[u] = best; } // Final component id for each column u: // t2 = bestTemp(minVal[u]), then component is the maximal interval containing u // where all humidities < t2 (i.e. max on interval < t2). compL_.assign(M_, 0); compR_.assign(M_, 0); for (int u = 0; u < M_; u++) { int t2 = bestTemp(minVal_[u]); if (t2 == -1) { compL_[u] = compR_[u] = u; } else { compL_[u] = leftBoundary(u, t2); compR_[u] = rightBoundary(u, t2); } } } bool can_reach(int /*L*/, int /*R*/, int S, int D) { // L=0, R=M-1 always in this version. return (compL_[S] == compL_[D] && compR_[S] == compR_[D]); }