#include <bits/stdc++.h> #include "obstacles.h" using namespace std; vector<int> T, H; int N, M; vector<int> max_reach; // max row reachable from row 0 in each column void initialize(vector<int> _T, vector<int> _H) { T = _T; H = _H; N = T.size(); M = H.size(); // For each column, find the highest row that is free max_reach.assign(M, -1); for (int j = 0; j < M; j++) { int r = -1; for (int i = 0; i < N; i++) { if (T[i] > H[j]) r = i; } max_reach[j] = r; } // Make max_reach prefix maximum for fast queries for (int j = 1; j < M; j++) { max_reach[j] = max(max_reach[j], max_reach[j-1]); } } bool can_reach(int L, int R, int S, int D) { if (S > D) swap(S, D); // always go left-to-right int highest_row = (L == 0 ? max_reach[D] : max_reach[D] - max_reach[L-1]); // Check if there's a connected path from row 0 through columns L..R // If highest_row >= 0, path exists return (highest_row >= 0); }