#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int N, M;
vector<int> T_val, H_val;
vector<int> P;
vector<int> MaxT;
vector<int> global_reach;
const int MAXM = 200005;
const int LOGM = 19;
int max_st[LOGM][MAXM];
int min_idx_st[LOGM][MAXM];
int log_table[MAXM];
vector<int> L_bound_val;
vector<int> R_bound_val;
vector<vector<int>> up_jump;
void build_sparse_table() {
log_table[1] = 0;
for (int i = 2; i <= M; i++) {
log_table[i] = log_table[i / 2] + 1;
}
for (int i = 0; i < M; i++) {
max_st[0][i] = H_val[i];
min_idx_st[0][i] = i;
}
for (int j = 1; j < LOGM; j++) {
for (int i = 0; i + (1 << j) <= M; i++) {
max_st[j][i] = max(max_st[j - 1][i], max_st[j - 1][i + (1 << (j - 1))]);
int left_idx = min_idx_st[j - 1][i];
int right_idx = min_idx_st[j - 1][i + (1 << (j - 1))];
if (H_val[left_idx] <= H_val[right_idx]) {
min_idx_st[j][i] = left_idx;
} else {
min_idx_st[j][i] = right_idx;
}
}
}
}
int query_max(int L, int R) {
int j = log_table[R - L + 1];
return max(max_st[j][L], max_st[j][R - (1 << j) + 1]);
}
int query_min_idx(int L, int R) {
int j = log_table[R - L + 1];
int left_idx = min_idx_st[j][L];
int right_idx = min_idx_st[j][R - (1 << j) + 1];
if (H_val[left_idx] <= H_val[right_idx]) return left_idx;
return right_idx;
}
int get_F(int h) {
int l = 0, r = N - 1, ans = N;
while (l <= r) {
int mid = l + (r - l) / 2;
if (P[mid] <= h) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
if (ans == 0) return 0;
return MaxT[ans - 1];
}
int get_left(int curr, int limit, int L_bound) {
int l = L_bound, r = curr, ans = curr;
while (l <= r) {
int mid = l + (r - l) / 2;
if (query_max(mid, curr) < limit) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return ans;
}
int get_right(int curr, int limit, int R_bound) {
int l = curr, r = R_bound, ans = curr;
while (l <= r) {
int mid = l + (r - l) / 2;
if (query_max(curr, mid) < limit) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return ans;
}
int simulate(int S, int L, int R, int req) {
int curr = S;
// 1. Fast unconstrained jumps in O(log M)
for (int k = LOGM - 1; k >= 0; k--) {
int nxt = up_jump[k][curr];
if (nxt == curr) continue;
int un_l = L_bound_val[nxt] + 1;
int un_r = R_bound_val[nxt] - 1;
// We only take the fast jump if the target's unconstrained interval fits strictly in [L, R]
if (un_l >= L && un_r <= R) {
curr = nxt;
}
}
// 2. Fallback to manual simulation (guaranteed to take very few steps now)
int curr_h = H_val[curr];
while (true) {
int T_curr = get_F(curr_h);
if (T_curr > req) return T_curr;
int l = get_left(curr, T_curr, L);
int r = get_right(curr, T_curr, R);
int nxt = query_min_idx(l, r);
if (nxt == curr) return T_curr; // completely stuck
curr = nxt;
curr_h = H_val[curr];
}
}
void initialize(std::vector<int> T, std::vector<int> H) {
N = T.size();
M = H.size();
T_val = T;
H_val = H;
P.resize(N);
MaxT.resize(N);
P[0] = T[0];
MaxT[0] = T[0];
for (int i = 1; i < N; i++) {
P[i] = min(P[i - 1], T[i]);
MaxT[i] = max(MaxT[i - 1], T[i]);
}
build_sparse_table();
L_bound_val.resize(M);
R_bound_val.resize(M);
up_jump.assign(LOGM, vector<int>(M));
// Precalculate unconstrained boundaries mapping for fast jumping
for (int i = 0; i < M; i++) {
int T_curr = get_F(H_val[i]);
L_bound_val[i] = get_left(i, T_curr, 0) - 1;
R_bound_val[i] = get_right(i, T_curr, M - 1) + 1;
}
for (int i = 0; i < M; i++) {
int l = L_bound_val[i] + 1;
int r = R_bound_val[i] - 1;
up_jump[0][i] = query_min_idx(l, r);
}
for (int j = 1; j < LOGM; j++) {
for (int i = 0; i < M; i++) {
up_jump[j][i] = up_jump[j - 1][up_jump[j - 1][i]];
}
}
global_reach.assign(M, -1);
// Precalculate full-bound reachability rapidly using the fast jump table
for (int S = 0; S < M; S++) {
int curr = S;
for (int k = LOGM - 1; k >= 0; k--) {
curr = up_jump[k][curr];
}
global_reach[S] = get_F(H_val[curr]);
}
}
bool can_reach(int L, int R, int S, int D) {
int req = query_max(min(S, D), max(S, D));
if (L == 0 && R == M - 1) {
return global_reach[S] > req && global_reach[D] > req;
}
int reach_S = simulate(S, L, R, req);
if (reach_S <= req) return false;
int reach_D = simulate(D, L, R, req);
return reach_D > req;
}
