#include <vector>
#include <algorithm>
#include <iostream>
#include <numeric>
using namespace std;
// Disjoint Set Union (DSU) structure
struct DSU {
vector<int> parent;
DSU(int n) {
parent.resize(n);
iota(parent.begin(), parent.end(), 0);
}
int find(int i) {
if (parent[i] == i)
return i;
return parent[i] = find(parent[i]);
}
void unite(int i, int j) {
int root_i = find(i);
int root_j = find(j);
if (root_i != root_j) {
parent[root_i] = root_j;
}
}
};
static DSU* dsu_ptr = nullptr;
void initialize(std::vector<int> T, std::vector<int> H) {
int N = T.size();
int M = H.size();
// 1. Precompute Prefix Min and Max for T
// PMin[k] = min(T[0]...T[k])
// PMax[k] = max(T[0]...T[k])
vector<int> PMin(N), PMax(N);
PMin[0] = T[0];
PMax[0] = T[0];
for (int i = 1; i < N; i++) {
PMin[i] = min(PMin[i - 1], T[i]);
PMax[i] = max(PMax[i - 1], T[i]);
}
// 2. Compute BaseMaxT for each column
// BaseMaxT[j] = max T reachable from (0, j) moving only vertically
vector<int> BaseMaxT(M);
// PMin is non-increasing. We can use binary search (upper_bound logic)
// to find the largest k such that PMin[k] > H[j].
// Since PMin is descending, we can use std::upper_bound with a custom comparator
// or just checking rbegin. simpler to write manual binary search or just use existing structure.
// PMin: [10, 8, 5, 2]. We want last index where val > H[j].
for (int j = 0; j < M; j++) {
int h = H[j];
if (T[0] <= h) {
BaseMaxT[j] = -1; // Cannot even exist at (0, j)
continue;
}
// Binary search for the deepest reachable row
int low = 0, high = N - 1;
int deepest = 0;
while (low <= high) {
int mid = low + (high - low) / 2;
if (PMin[mid] > h) {
deepest = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
BaseMaxT[j] = PMax[deepest];
}
// 3. Propagate Reachability
vector<int> Reach(M);
// Left to Right
int current_cap = -1;
for (int j = 0; j < M; j++) {
if (current_cap > H[j]) {
// Can enter from left
current_cap = max(current_cap, BaseMaxT[j]);
} else {
// Cannot enter from left, reset to base
current_cap = BaseMaxT[j];
}
Reach[j] = current_cap;
}
// Right to Left
current_cap = -1;
for (int j = M - 1; j >= 0; j--) {
if (current_cap > H[j]) {
current_cap = max(current_cap, BaseMaxT[j]);
} else {
current_cap = BaseMaxT[j];
}
Reach[j] = max(Reach[j], current_cap);
}
// 4. Build DSU
if (dsu_ptr) delete dsu_ptr;
dsu_ptr = new DSU(M);
for (int j = 0; j < M - 1; j++) {
// We can move between j and j+1 if the Reachability at j is enough to cross H[j+1]
// OR if Reachability at j+1 is enough to cross H[j].
if (Reach[j] > H[j+1] || Reach[j+1] > H[j]) {
dsu_ptr->unite(j, j + 1);
}
}
}
bool can_reach(int L, int R, int S, int D) {
// For L=0, R=M-1 subtask, we ignore L and R.
return dsu_ptr->find(S) == dsu_ptr->find(D);
}
