#include <vector>
using namespace std;
const int MAXM = 200005;
int parent[MAXM];
int find(int x) {
return parent[x] == x ? x : parent[x] = find(parent[x]);
}
void unite(int x, int y) {
parent[find(x)] = find(y);
}
vector<int> T_global, H_global;
vector<bool> free_cell; // free_cell[j] = T[0] > H[j]
void initialize(vector<int> T, vector<int> H) {
T_global = T;
H_global = H;
int M = H.size();
// mark which columns are free at row 0
free_cell.assign(M, false);
for (int j = 0; j < M; ++j) {
if (T[0] > H[j]) {
free_cell[j] = true;
}
}
// initialize DSU
for (int j = 0; j < M; ++j) parent[j] = j;
// merge adjacent free columns in row 0
for (int j = 0; j + 1 < M; ++j) {
if (free_cell[j] && free_cell[j + 1]) {
unite(j, j + 1);
}
}
// check for vertical paths via other rows
int N = T.size();
for (int i = 1; i < N; ++i) {
int t = T[i];
int prev = -1;
for (int j = 0; j < M; ++j) {
if (t > H[j]) {
if (free_cell[j]) {
if (prev != -1) unite(prev, j);
prev = j;
}
} else {
prev = -1;
}
}
}
}
bool can_reach(int L, int R, int S, int D) {
if (find(S) != find(D)) return false;
// check that all connectivity is within L to R
if (S < L || S > R || D < L || D > R) return false;
return true;
}
