#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <tuple>
using namespace std;
const int INF = 2e9;
// ------------------------------------------------------------
// Segment Tree for Maximum values (finds value > x)
// ------------------------------------------------------------
struct SegTreeMax {
int n;
vector<int> tree;
SegTreeMax(const vector<int>& arr) {
n = arr.size();
tree.resize(4 * n, -INF);
build(1, 0, n - 1, arr);
}
void build(int node, int start, int end, const vector<int>& arr) {
if (start == end) {
tree[node] = arr[start];
} else {
int mid = (start + end) / 2;
build(2 * node, start, mid, arr);
build(2 * node + 1, mid + 1, end, arr);
tree[node] = max(tree[2 * node], tree[2 * node + 1]);
}
}
// Find first index >= l with value > x
// Returns n if not found
int first_greater(int l, int x) {
return _first_greater(1, 0, n - 1, l, x);
}
int _first_greater(int node, int start, int end, int l, int x) {
// 如果当前区间完全在 l 左边，或者区间最大值都 <= x，直接返回无解
if (end < l || tree[node] <= x) {
return n;
}
if (start == end) {
return start;
}
int mid = (start + end) / 2;
// 优先查左边
int res = _first_greater(2 * node, start, mid, l, x);
if (res != n) return res;
// 左边没找到查右边
return _first_greater(2 * node + 1, mid + 1, end, l, x);
}
};
// ------------------------------------------------------------
// Segment Tree for Minimum values (finds value <= x)
// ------------------------------------------------------------
struct SegTreeMin {
int n;
vector<int> tree;
SegTreeMin(const vector<int>& arr) {
n = arr.size();
tree.resize(4 * n, INF);
build(1, 0, n - 1, arr);
}
void build(int node, int start, int end, const vector<int>& arr) {
if (start == end) {
tree[node] = arr[start];
} else {
int mid = (start + end) / 2;
build(2 * node, start, mid, arr);
build(2 * node + 1, mid + 1, end, arr);
tree[node] = min(tree[2 * node], tree[2 * node + 1]);
}
}
// Find first index >= l with value <= x
// Returns n if not found
int first_leq(int l, int x) {
return _first_leq(1, 0, n - 1, l, x);
}
int _first_leq(int node, int start, int end, int l, int x) {
if (end < l || tree[node] > x) {
return n;
}
if (start == end) {
return start;
}
int mid = (start + end) / 2;
int res = _first_leq(2 * node, start, mid, l, x);
if (res != n) return res;
return _first_leq(2 * node + 1, mid + 1, end, l, x);
}
// Find last index <= r with value <= x
// Returns -1 if not found
int last_leq(int r, int x) {
return _last_leq(1, 0, n - 1, r, x);
}
int _last_leq(int node, int start, int end, int r, int x) {
if (start > r || tree[node] > x) {
return -1;
}
if (start == end) {
return start;
}
int mid = (start + end) / 2;
// 优先尝试右边，因为我们要找的是 last (最大的 index)
int res = -1;
if (mid + 1 <= r) { // 只有右子树在范围内才尝试
res = _last_leq(2 * node + 1, mid + 1, end, r, x);
}
if (res != -1) return res;
return _last_leq(2 * node, start, mid, r, x);
}
};
// ------------------------------------------------------------
// Global Data
// ------------------------------------------------------------
int N, M;
vector<int> T_arr;
vector<int> H_arr;
SegTreeMax* seg_max_ptr = nullptr;
SegTreeMin* seg_min_ptr = nullptr;
void initialize(const vector<int>& T, const vector<int>& H) {
T_arr = T;
H_arr = H;
N = T.size();
M = H.size();
// 清理旧内存（如果是多组数据）
if (seg_max_ptr) delete seg_max_ptr;
if (seg_min_ptr) delete seg_min_ptr;
seg_max_ptr = new SegTreeMax(T_arr);
seg_min_ptr = new SegTreeMin(T_arr);
}
// ------------------------------------------------------------
// Query Logic
// ------------------------------------------------------------
// Helper: 找到包含 row i 的自由区间的右端点
// 即找到 i 之后第一个障碍物的位置 - 1
int interval_end(int col, int i) {
int blk = seg_min_ptr->first_leq(i + 1, H_arr[col]);
return (blk == N) ? N - 1 : blk - 1;
}
bool can_reach(int L_ignore, int R_ignore, int S, int D) {
if (S == D) return true;
// 初始区间：列 S，包含行 0
int start_end = interval_end(S, 0);
// BFS 队列: (col, L, R)
deque<tuple<int, int, int>> q;
q.push_back({S, 0, start_end});
// Visited: (col, L_start)
// 使用 set 比较慢，如果 N*M 很大且内存允许，可用 vector<vector<bool>>
set<pair<int, int>> visited;
visited.insert({S, 0});
while (!q.empty()) {
auto [col, Lint, Rint] = q.front();
q.pop_front();
// 检查是否到达目标
// 题目要求到达 (0, D)。如果当前区间在 D 列且包含 0 行 (Lint == 0)，则成功
if (col == D && Lint == 0) {
return true;
}
// 尝试左右邻居
int neighbors[] = {col - 1, col + 1};
for (int nb : neighbors) {
if (nb < 0 || nb >= M) continue;
// 在邻居列 nb 中，寻找所有与 [Lint, Rint] 重叠的自由区间
// 从 Lint 开始寻找第一个自由行 (T > H[nb])
int y = seg_max_ptr->first_greater(Lint, H_arr[nb]);
while (y != N && y <= Rint) {
// 找到了一个重叠点 y，现在需要确定这个点所在的完整自由区间 [nb_start, nb_end]
// 1. 找区间终点
int nb_end = interval_end(nb, y);
// 2. 找区间起点
// 找到 y 及其上方最近的一个障碍物
int obstacle_above = seg_min_ptr->last_leq(y, H_arr[nb]);
int nb_start = (obstacle_above != -1) ? obstacle_above + 1 : 0;
if (visited.find({nb, nb_start}) == visited.end()) {
visited.insert({nb, nb_start});
q.push_back({nb, nb_start, nb_end});
}
// 继续在 [Lint, Rint] 范围内找下一个不连续的区间
// 从当前 nb 区间结束后的一行开始找
if (nb_end + 1 < N) {
y = seg_max_ptr->first_greater(nb_end + 1, H_arr[nb]);
} else {
y = N;
}
}
}
}
return false;
}
