// Your solution code here
#include <bits/stdc++.h>
using namespace std;
// ---------- DSU ----------
struct DSU {
vector<int> p, r;
DSU() {}
DSU(int n) { init(n); }
void init(int n) {
p.resize(n);
r.assign(n, 0);
iota(p.begin(), p.end(), 0);
}
int find(int x) {
while (p[x] != x) {
p[x] = p[p[x]];
x = p[x];
}
return x;
}
void unite(int a, int b) {
a = find(a); b = find(b);
if (a == b) return;
if (r[a] < r[b]) swap(a, b);
p[b] = a;
if (r[a] == r[b]) r[a]++;
}
};
// ---------- Fenwick (BIT) for counts + kth ----------
struct BIT {
int n;
vector<int> bit; // 1-based
BIT() : n(0) {}
BIT(int n_) { init(n_); }
void init(int n_) {
n = n_;
bit.assign(n + 1, 0);
}
void add(int idx, int delta) {
for (int i = idx + 1; i <= n; i += i & -i) bit[i] += delta;
}
int sumPrefix(int idx) const { // sum [0..idx], idx<0 => 0
if (idx < 0) return 0;
int s = 0;
for (int i = idx + 1; i > 0; i -= i & -i) s += bit[i];
return s;
}
// smallest pos such that prefix sum >= k (k is 1-based). returns 0-based pos.
int find_kth(int k) const {
int idx = 0;
int bitmask = 1 << (31 - __builtin_clz(n)); // highest power of 2 <= n
while (bitmask) {
int nxt = idx + bitmask;
if (nxt <= n && bit[nxt] < k) {
idx = nxt;
k -= bit[nxt];
}
bitmask >>= 1;
}
return idx; // 0-based position
}
};
// ---------- Globals filled by initialize ----------
static DSU g_dsu;
static int gM = 0;
// segment tree for range max on H
struct SegMax {
int n; // original size
int size; // power-of-two
vector<int> seg;
void build(const vector<int>& a) {
n = (int)a.size();
size = 1;
while (size < n) size <<= 1;
seg.assign(2 * size, INT_MIN);
for (int i = 0; i < n; i++) seg[size + i] = a[i];
for (int i = size - 1; i >= 1; i--) seg[i] = max(seg[2 * i], seg[2 * i + 1]);
}
int range_max(int l, int r) const { // inclusive
if (l > r) return INT_MIN;
l += size; r += size;
int res = INT_MIN;
while (l <= r) {
if (l & 1) res = max(res, seg[l++]);
if (!(r & 1)) res = max(res, seg[r--]);
l >>= 1; r >>= 1;
}
return res;
}
};
static SegMax g_seg;
// ---------- Core algorithm ----------
void initialize(std::vector<int> T, std::vector<int> H) {
int N = (int)T.size();
int M = (int)H.size();
gM = M;
// prefix minima of temperatures
vector<int> pref_min(N);
int cur_min = T[0];
for (int i = 0; i < N; i++) {
cur_min = min(cur_min, T[i]);
pref_min[i] = cur_min;
}
// depth[col] = largest row i such that min(T[0..i]) > H[col]
vector<int> depth(M, -1);
for (int j = 0; j < M; j++) {
int h = H[j];
int lo = 0, hi = N - 1, ans = -1;
while (lo <= hi) {
int mid = (lo + hi) >> 1;
if (pref_min[mid] > h) {
ans = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
depth[j] = ans;
}
// bucket columns by exact depth
vector<vector<int>> cols_by_depth(N);
for (int j = 0; j < M; j++) {
int d = depth[j];
if (d >= 0) cols_by_depth[d].push_back(j);
}
// segment tree for max(H) queries
g_seg.build(H);
// DSU over columns
g_dsu.init(M);
// BIT: active columns are those with depth >= current row i
BIT bit(M);
// Process rows from bottom to top; when at row i, activate columns with depth == i.
for (int i = N - 1; i >= 0; i--) {
for (int col : cols_by_depth[i]) {
bit.add(col, 1);
// ----- nearest active on the left -----
int cnt_left = bit.sumPrefix(col - 1);
if (cnt_left > 0) {
int left = bit.find_kth(cnt_left); // rightmost active < col
if (left + 1 <= col - 1) {
if (g_seg.range_max(left + 1, col - 1) < T[i]) {
g_dsu.unite(left, col);
}
} else {
g_dsu.unite(left, col);
}
}
// ----- nearest active on the right -----
int total_active = bit.sumPrefix(M - 1);
int cnt_up_to_col = bit.sumPrefix(col); // includes col
if (total_active > cnt_up_to_col) {
int right = bit.find_kth(cnt_up_to_col + 1); // leftmost active > col
if (col + 1 <= right - 1) {
if (g_seg.range_max(col + 1, right - 1) < T[i]) {
g_dsu.unite(col, right);
}
} else {
g_dsu.unite(col, right);
}
}
}
}
}
bool can_reach(int /*L*/, int /*R*/, int S, int D) {
// L=0 and R=M-1 always in this version.
return g_dsu.find(S) == g_dsu.find(D);
}
