#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
const int N_MAX = 2e5 + 11;
struct MM {
MM(int x) : mx(x), mn(x) {};
MM(int x, int y) : mx(x), mn(y) {};
int mx, mn;
MM operator+ (const MM& o) const {
return MM(max(mx, o.mx), min(mn, o.mn));
}
};
struct SegTree {
int T[N_MAX << 2];
void build(vector<int>& A, int v, int l, int r) {
if (l == r) T[v] = A[l];
else {
int m = (l + r) / 2;
build(A, v * 2 + 1, l, m);
build(A, v * 2 + 2, m + 1, r);
T[v] = max(T[v * 2 + 1], T[v * 2 + 2]);
}
}
int query(int ql, int qr, int v, int l, int r) {
if (ql <= l && r <= qr) return T[v];
if (qr < l || r < ql) return -1;
int m = (l + r) / 2;
int qa = query(ql, qr, v * 2 + 1, l, m);
int qb = query(ql, qr, v * 2 + 2, m + 1, r);
return max(qa, qb);
}
} ST;
struct DSU {
vector<MM> M; vector<int> P, life, L, R;
DSU () = default;
DSU (vector<int> H) {
int N = H.size();
for (int i = 0; i < N; i++) {
M.push_back(H[i]);
P.push_back(i);
L.push_back(i);
R.push_back(i);
life.push_back(1);
}
}
int f(int x) { return x == P[x] ? x : P[x] = f(P[x]); }
void g(int x, int y) {
x = f(x), y = f(y); if (x == y) return;
// cout << "G " << x << ' ' << y << endl;
M[x] = M[x] + M[y]; P[y] = x; life[x] += life[y];
L[x] = min(L[x], L[y]), R[x] = max(R[x], R[y]);
}
MM h(int x) {
return M[f(x)];
}
};
DSU dsu;
int lowest[N_MAX];
vector<int> T, H;
void initialize(vector<int> T, vector<int> H) {
::T = T; ::H = H; T.push_back(0);
fill(lowest, lowest + N_MAX, -(1 << 30));
int N = T.size(), M = H.size();
dsu = DSU(H); ST.build(H, 0, 0, M - 1);
set<pair<int, int>> high, low;
for (int i = 0; i < M - 1; i++) {
high.insert({max(H[i], H[i + 1]), i});
}
for (int i = 0; i < M; i++) {
low.insert({H[i], i});
}
for (int i = 0; i < N; i++) {
// cout << "H " << i << endl;
while (!high.empty() && high.begin()->first < T[i]) {
int x = high.begin()->second;
dsu.g(x, x + 1);
high.erase(high.begin());
}
// if (!low.empty()) {
// cout << "CMP " << low.begin()->first << ' ' << T[i] << endl;
// }
while (!low.empty() && (--low.end())->first >= T[i]) {
int x = (--low.end())->second;
int y = dsu.f(x);
if (--dsu.life[y] == 0) {
// cout << "S " << dsu.L[y] << ' ' << dsu.R[y] << ' ' << i - 1 << endl;
for (int j = dsu.L[y]; j <= dsu.R[y]; j++) {
if (lowest[j] == -(1 << 30)) {
lowest[j] = i - 1;
}
}
}
low.erase(--low.end());
}
}
for (int i = 1; i < T.size(); i++) {
::T[i] = max(::T[i - 1], ::T[i]);
}
}
bool can_reach(int L, int R, int S, int D) {
if (S > D) swap(S, D);
int maxH = ST.query(S, D, 0, 0, (int) H.size() - 1);
int req = upper_bound(T.begin(), T.end(), maxH) - T.begin();
// for (int x : T) cout << x << ' '; cout << endl;
// cout << maxH << ' ' << T[0] << endl;
// cout << req << ' ' << lowest[S] << ' ' << lowest[D] << endl;
return lowest[S] >= req && lowest[D] >= req;
}
