#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);
}
