#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
using ii = pair<int, int>;
using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
using pll = pair<ll, ll>;
#define fst first
#define snd second
#define pb push_back
#define eb emplace_back
struct DSU {
vi par, mini, maxi, tim;
vector<ii> edges;
DSU(int n) : par(n), mini(n), maxi(n), tim(n, 0) {
iota(all(par), 0);
mini = maxi = par;
}
int find(int x) {
if (par[x] == x) return x;
return par[x] = find(par[x]);
}
bool unite(int x, int y, int t) {
x = find(x), y = find(y);
if (x == y) return false;
int p = sz(par);
par[x] = p, par[y] = p;
par.pb(p);
mini.pb(min(mini[x], mini[y]));
maxi.pb(max(maxi[x], maxi[y]));
tim.pb(t);
edges.eb(p, x);
edges.eb(p, y);
return true;
}
};
const int INF = 1e9;
struct SegTree {
int n;
vi st;
SegTree(vi &v) {
n = 1; while (n < sz(v)) n *= 2;
st.assign(2 * n, INF);
forn(i, sz(v)) st[i + n] = v[i];
dforsn(i, 1, n) st[i] = min(st[2 * i], st[2 * i + 1]);
}
int query(int l, int r) {
int ret = INF;
for (l += n, r += n; l < r; l /= 2, r /= 2) {
if (l & 1) ret = min(ret, st[l++]);
if (r & 1) ret = min(st[--r], ret);
}
return ret;
}
int find(int s, int e, int k, tuple<int, int, int> node, bool t) {
auto [l, r, u] = node;
if (e <= l || r <= s || st[u] >= k) return -1;
if (r - l == 1) return l;
int m = (l + r) / 2;
tuple<int, int, int> a = {l, m, 2 * u}, b = {m, r, 2 * u + 1};
if (t) swap(a, b);
int ret = find(s, e, k, a, t);
if (ret != -1) return ret;
return find(s, e, k, b, t);
}
int find(int s, int e, int k, bool t) {
return find(s, e, k, {0, n, 1}, t);
}
};
DSU ret(0);
void initialize(vi T, vi H) {
const int n = sz(T), m = sz(H);
vector<bool> active(m, false);
DSU dsu(m);
vi order(m);
iota(all(order), 0);
sort(all(order), [&](const int &lhs, const int &rhs) {
return H[lhs] < H[rhs];
});
auto activate = [&](int i, int t) {
if (i > 0 && active[i - 1]) dsu.unite(i - 1, i, t);
if (i + 1 < m && active[i + 1]) dsu.unite(i, i + 1, t);
active[i] = true;
};
{
int maxi = -INF, j = 0;
forn(i, n) if (T[i] > maxi) {
maxi = T[i];
while (j < m && H[order[j]] < T[i]) {
activate(order[j++], i);
}
}
}
const int N = sz(dsu.par);
SegTree t(T), h(H);
ret = DSU(N);
forsn(i, n, N) ret.mini[i] = INF, ret.maxi[i] = -INF;
for (auto [p, u] : dsu.edges) {
int j = dsu.tim[p], i = dsu.tim[u];
if (i == j) {
ret.unite(u, p, -1);
continue;
}
int l = dsu.mini[u], r = dsu.maxi[u];
int k = t.query(i, j);
int first = h.find(l, r + 1, k, 0), last = h.find(l, r + 1, k, 1);
if (first != -1) {
assert(last != -1);
ret.unite(u, p, -1);
int par = ret.find(p);
ret.mini[par] = min(ret.mini[par], last);
ret.maxi[par] = max(ret.maxi[par], first);
}
}
}
bool can_reach(int L, int R, int S, int D) {
int p = ret.find(S);
return ret.find(D) == p && ret.mini[p] >= L && ret.maxi[p] <= R;
}
