#include <bits/stdc++.h>
using namespace std;
// ---------- DSU ----------
struct DSU {
vector<int> p, sz;
DSU(int n = 0) { init(n); }
void init(int n) {
p.resize(n);
sz.assign(n, 1);
iota(p.begin(), p.end(), 0);
}
int find(int x) {
return p[x] == x ? x : p[x] = find(p[x]);
}
void unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
if (sz[a] < sz[b]) swap(a, b);
p[b] = a;
sz[a] += sz[b];
}
};
// ---------- Segment Tree for range maximum ----------
struct SegTree {
int n;
vector<int> seg;
SegTree() {}
explicit SegTree(const vector<int>& a) { build(a); }
void build(const vector<int>& a) {
n = (int)a.size();
seg.assign(4 * n, 0);
build(1, 0, n - 1, a);
}
void build(int node, int l, int r, const vector<int>& a) {
if (l == r) {
seg[node] = a[l];
return;
}
int mid = (l + r) >> 1;
build(node << 1, l, mid, a);
build(node << 1 | 1, mid + 1, r, a);
seg[node] = max(seg[node << 1], seg[node << 1 | 1]);
}
int query(int L, int R) const { return query(1, 0, n - 1, L, R); }
int query(int node, int l, int r, int L, int R) const {
if (R < l || r < L) return INT_MIN;
if (L <= l && r <= R) return seg[node];
int mid = (l + r) >> 1;
return max(query(node << 1, l, mid, L, R),
query(node << 1 | 1, mid + 1, r, L, R));
}
};
// ---------- Global data ----------
vector<int> T, H;
vector<int> depth; // max continuous prefix where column stays free
vector<int> col2int; // column -> interval id (or -1)
vector<int> prefMaxT; // prefix maximum of T
struct Interval {
int left, right;
int maxDepth; // max depth among its columns
int Tval; // prefixMaxT[maxDepth]
int id;
};
vector<Interval> intervals;
DSU dsu;
SegTree seg;
// ---------- Helper to compute depth ----------
void computeDepth() {
int N = T.size(), M = H.size();
depth.assign(M, N - 1);
// rows sorted by temperature (value, index)
vector<pair<int, int>> rows;
rows.reserve(N);
for (int i = 0; i < N; ++i) rows.emplace_back(T[i], i);
sort(rows.begin(), rows.end()); // ascending by temperature
// columns sorted by humidity
vector<int> colIdx(M);
iota(colIdx.begin(), colIdx.end(), 0);
sort(colIdx.begin(), colIdx.end(),
[&](int a, int b) { return H[a] < H[b]; });
const int INF = INT_MAX;
int rp = 0;
int curMin = INF;
for (int idx : colIdx) {
while (rp < N && rows[rp].first <= H[idx]) {
curMin = min(curMin, rows[rp].second);
++rp;
}
if (curMin == INF) depth[idx] = N - 1;
else depth[idx] = curMin - 1;
}
}
// ---------- Helper to build intervals on row 0 ----------
void buildIntervals() {
int M = H.size();
intervals.clear();
col2int.assign(M, -1);
int i = 0;
while (i < M) {
if (T[0] > H[i]) {
int start = i;
int maxH = H[i];
int maxDepth = depth[i];
++i;
while (i < M && T[0] > H[i]) {
maxH = max(maxH, H[i]);
maxDepth = max(maxDepth, depth[i]);
++i;
}
Interval it;
it.left = start;
it.right = i - 1;
it.maxDepth = maxDepth;
it.Tval = 0; // will be set later after prefixMaxT known
it.id = intervals.size();
intervals.push_back(it);
int id = it.id;
for (int j = start; j <= i - 1; ++j) col2int[j] = id;
} else {
++i;
}
}
int K = intervals.size();
for (int id = 0; id < K; ++id) {
intervals[id].Tval = prefMaxT[intervals[id].maxDepth];
}
}
// ---------- Main initialization ----------
void initialize(vector<int> T_, vector<int> H_) {
T.swap(T_);
H.swap(H_);
int N = T.size();
int M = H.size();
// prefix maximum of temperatures
prefMaxT.assign(N, 0);
prefMaxT[0] = T[0];
for (int i = 1; i < N; ++i) prefMaxT[i] = max(prefMaxT[i - 1], T[i]);
// compute depth for each column
computeDepth();
// build intervals on the first row
buildIntervals();
// initialise DSU and segment tree
int K = intervals.size();
dsu.init(K);
seg = SegTree(H);
// sort interval ids by decreasing Tval (break ties by left coordinate)
vector<int> order(K);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(),
[&](int a, int b) {
if (intervals[a].Tval != intervals[b].Tval)
return intervals[a].Tval > intervals[b].Tval;
return intervals[a].left < intervals[b].left;
});
// active set ordered by left endpoint
set<pair<int, int>> active; // (left, interval id)
for (int idx : order) {
const Interval &cur = intervals[idx];
int curT = cur.Tval;
// locate where this interval would be inserted
auto itSucc = active.lower_bound({cur.left, -1});
// predecessor (the greatest left < cur.left)
if (itSucc != active.begin()) {
auto itPrev = prev(itSucc);
int pid = itPrev->second;
const Interval &p = intervals[pid];
int regionMax = seg.query(p.left, cur.right);
if (regionMax < curT) dsu.unite(pid, idx);
}
// successor (the smallest left >= cur.left)
if (itSucc != active.end()) {
int sid = itSucc->second;
const Interval &s = intervals[sid];
int regionMax = seg.query(cur.left, s.right);
if (regionMax < curT) dsu.unite(idx, sid);
}
active.insert({cur.left, idx});
}
}
// ---------- Query ----------
bool can_reach(int L, int R, int S, int D) {
// For the sub‑problem L=0,R=M-1, we can ignore L,R.
int idS = col2int[S];
int idD = col2int[D];
if (idS == -1 || idD == -1) return false; // should not happen for valid queries
if (idS == idD) return true;
return dsu.find(idS) == dsu.find(idD);
}
