// Your solution code here
#include <bits/stdc++.h>
using namespace std;
/*
NOTE:
This solution treats the set of cells reachable from row 0 as the "top-prefix" open area
in each column, i.e., rows 0..height[j]-1 where all those cells are free of vegetation.
Then (0,S) can reach (0,D) iff every column between them is open in row 0 (no gaps).
This matches the simplified condition:
cell (0,j) is open <=> T[0] > H[j]
and connectivity on row 0 is just contiguous open columns.
It is very fast: O((N+M) + Q log M).
*/
static int N_, M_;
static vector<int> T_, H_;
static vector<int> openTopPrefixMin; // prefix min of T
static vector<int> openTop; // 1 if (0,j) is open
static vector<int> segMin; // segment tree for range-min of openTop
static void buildSeg(int idx, int l, int r) {
if (l == r) {
segMin[idx] = openTop[l];
return;
}
int mid = (l + r) >> 1;
buildSeg(idx << 1, l, mid);
buildSeg(idx << 1 | 1, mid + 1, r);
segMin[idx] = min(segMin[idx << 1], segMin[idx << 1 | 1]);
}
static int querySeg(int idx, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return segMin[idx];
int mid = (l + r) >> 1;
int ans = 1;
if (ql <= mid) ans = min(ans, querySeg(idx << 1, l, mid, ql, qr));
if (qr > mid) ans = min(ans, querySeg(idx << 1 | 1, mid + 1, r, ql, qr));
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();
// openTop[j] = 1 iff T[0] > H[j]
openTop.assign(M_, 0);
for (int j = 0; j < M_; j++) {
openTop[j] = (T_[0] > H_[j]) ? 1 : 0;
}
// Build segtree for range min over openTop
segMin.assign(4 * max(1, M_), 1);
if (M_ > 0) buildSeg(1, 0, M_ - 1);
}
bool can_reach(int L, int R, int S, int D) {
(void)L; (void)R; // per statement here, L=0 and R=M-1 always
if (S == D) return true;
int a = min(S, D), b = max(S, D);
// Path exists along the top row iff all columns in [a..b] are open on row 0.
// (Given (0,S) and (0,D) are guaranteed open, this mainly checks for gaps.)
int mn = querySeg(1, 0, M_ - 1, a, b);
return mn == 1;
}
