#include <bits/stdc++.h> #include "obstacles.h" using namespace std; vector<int> T, H; int N, M; vector<int> max_row; // highest free row in each column void initialize(vector<int> _T, vector<int> _H) { T = _T; H = _H; N = T.size(); M = H.size(); max_row.assign(M, -1); for (int j = 0; j < M; j++) { for (int i = N-1; i >= 0; i--) { // scan top-down to find highest free row if (T[i] > H[j]) { max_row[j] = i; break; } } } // optional: no prefix/suffix needed if we scan range in can_reach } bool can_reach(int L, int R, int S, int D) { if (S > D) swap(S, D); int min_row = max_row[L]; for (int j = L+1; j <= R; j++) min_row = min(min_row, max_row[j]); // path exists only if all columns in [L,R] have at least one free row return min_row >= 0; }