#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
struct rmq {
vector<pair<int, int>> st;
size_t sz;
rmq() = default;
rmq(vector<int> a) {
sz = 1;
while (sz < a.size()) {
sz <<= 1;
}
st.resize(2 * sz, make_pair(0, -1));
for (int i = 0; i < a.size(); i++) {
st[i + sz] = {a[i], i};
}
for (int i = sz - 1; i > 0; i--) {
st[i] = min(st[2 * i], st[2 * i + 1]);
}
}
pair<int, int> get(int l, int r) {
l += sz; r += sz;
pair<int, int> res = {INT32_MAX, -1};
while (l <= r) {
if (l & 1) {
res = min(res, st[l++]);
}
if (~r & 1) {
res = min(res, st[r--]);
}
l >>= 1;
r >>= 1;
}
return res;
}
};
vector<int> ord;
struct forest {
vector<int> d;
vector<vector<pair<int, int>>> binup;
int timer;
void add_vertice(int idx, int p) {
// cout << "! " << idx << ' ' << p << '\n';
ord[idx] = timer++;
if (p == -1) {
d[idx] = 0;
for (int l = 0; l < binup.size(); l++) {
binup[l][idx] = {idx, idx};
}
return;
}
d[idx] = d[p] + 1;
binup[0][idx] = {p, max(idx, p)};
for (int l = 1; l < binup.size(); l++) {
binup[l][idx] = {binup[l - 1][binup[l - 1][idx].first].first, max(binup[l - 1][binup[l - 1][idx].first].second, binup[l - 1][idx].second)};
}
}
pair<int, int> up(int idx, int amount) {
pair<int, int> res = {idx, idx};
for (int l = binup.size() - 1; l >= 0; l--) {
if (amount & (1 << l)) {
res.second = max(res.second, binup[l][res.first].second);
res.first = binup[l][res.first].first;
}
}
return res;
}
forest() = default;
forest(vector<int> t, vector<int> h) {
d.resize(h.size());
ord.resize(h.size());
timer = 0;
binup.resize(20);
for (int i = 0; i < binup.size(); i++) {
binup[i].resize(h.size());
}
int cur = t.size();
int now = 0;
rmq tmin(t), tmax;
{
vector<int> tmp = t;
for (int i = 0; i < tmp.size(); i++) {
tmp[i] *= -1;
}
tmax = rmq(tmp);
}
vector<pair<int, int>> sh;
for (int i = 0; i < h.size(); i++) {
sh.emplace_back(h[i], i);
}
ranges::sort(sh);
int ptr = 0, ptr2 = sh.size() - 1;
set<int> closed, open;
while (cur > 0) {
// cout << "! " << cur << endl;
int next = -1;
if (!now) {
next = tmax.get(0, cur - 1).second;
int val = t[next];
while (ptr2 >= 0 && sh[ptr2].first >= val) {
closed.insert(sh[ptr2--].second);
}
}
if (now || next == 0) {
if (next == -1) {
next = tmin.get(0, cur - 1).second;
}
vector<int> nw;
int val = t[next];
while (ptr < sh.size() && sh[ptr].first < val) {
nw.push_back(sh[ptr++].second);
}
ranges::sort(nw);
for (int i : nw) {
auto sptr = open.lower_bound(i);
bool ok = true;
if (sptr == open.begin()) {
ok = false;
} else {
sptr--;
int free = *sptr;
auto sptr2 = closed.lower_bound(free);
if (sptr2 != closed.end() && *sptr2 <= i) {
ok = false;
}
}
if (ok) {
add_vertice(i, *sptr);
} else {
sptr = open.lower_bound(i);
ok = true;
if (sptr == open.end()) {
ok = false;
} else {
int free = *sptr;
auto sptr2 = closed.lower_bound(i);
if (sptr2 != closed.end() && *sptr2 <= free) {
ok = false;
}
}
if (ok) {
add_vertice(i, *sptr);
} else {
add_vertice(i, -1);
}
}
open.insert(i);
}
}
now = 1 - now;
cur = next;
}
for (int i = 0; i < h.size(); i++) {
if (open.find(i) == open.end()) {
add_vertice(i, -1);
}
}
}
};
forest l_forest, r_forest;
rmq hmin;
int n;
void initialize(vector<int> t, vector<int> h) {
l_forest = forest(t, h);
ranges::reverse(h);
r_forest = forest(t, h);
ranges::reverse(h);
hmin = rmq(ord);
n = h.size();
}
bool can_reach(int L, int R, int S, int D) {
if (S > D) swap(S, D);
int m = hmin.get(S, D).second;
int ds = r_forest.d[n - 1 - S];
int dd = l_forest.d[D];
int dmr = r_forest.d[n - 1 - m];
int dml = l_forest.d[m];
auto [rv, rb] = r_forest.up(n - 1 - S, ds - dmr);
auto [lv, lb] = l_forest.up(D, dd - dml);
if (rv != n - 1 - m || lv != m || lb > R || rb > n - 1 - L) return false;
return true;
}
