#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using pi = pair<int, int>;
struct SegTree {
int n; vi arr; vector<pi> st;
SegTree() {}
SegTree(int N, vi &Arr) {
n = N; arr = Arr; st.assign(4*n, {-1, -1});
build(0, 0, n);
}
pi combine(pi x, pi y) {
pi r = {-1, -1};
if (x.first < 0) r.first = y.first;
else if (y.first < 0) r.first = x.first;
else r.first = arr[x.first] < arr[y.first] ? x.first : y.first;
if (x.second < 0) r.second = y.second;
else if (y.second < 0) r.second = x.second;
else r.second = arr[x.second] > arr[y.second] ? x.second : y.second;
return r;
}
pi build(int i, int l, int r) {
if (l+1==r) return st[i] = {l, l};
int m = l + (r- l)/2;
return st[i] = combine(build(2*i+1, l, m), build(2*i+2, m, r));
}
pi query(int i, int l, int r, int ql, int qr) {
if (qr <= l || r <= ql) return {-1, -1};
if (ql <= l && r <= qr) return st[i];
int m = l + (r - l) / 2;
return combine(query(2*i+1, l, m, ql, qr), query(2*i+2, m, r, ql, qr));
}
// max i in [l, r] such that max([l, i]) < T or min([l, i]) > T
int right(int i, int l, int r, int ql, int qr, int T, bool mx) {
if (r <= ql || qr <= l) return -1;
if (ql <= l && r <= qr) {
if ((mx && (st[i].second >= 0 && arr[st[i].second] < T)) || (!mx && (st[i].first >= 0 && arr[st[i].first] > T))) return -1;
}
if (l + 1 == r) return ((mx && arr[l] >= T) || (!mx && arr[l] <= T)) ? l : -1;
int m = l + (r - l) / 2;
int left = right(2*i+1, l, m, ql, qr, T, mx);
if (left != -1) return left;
return right(2*i+2, m, r, ql, qr, T, mx);
}
// min i in [l, r] such that max([i, r]) < T or min([i, r]) > T
int left(int i, int l, int r, int ql, int qr, int T, bool mx) {
if (r <= ql || qr <= l) return -1;
if (ql <= l && r <= qr) {
if ((mx && (st[i].second >= 0 && arr[st[i].second] < T)) || (!mx && (st[i].first >= 0 && arr[st[i].first] > T))) return -1;
}
if (l + 1 == r) return ((mx && arr[l] >= T) || (!mx && arr[l] <= T)) ? l : -1;
int m = l + (r - l) / 2;
int right = left(2*i+2, m, r, ql, qr, T, mx);
if (right != -1) return right;
return left(2*i+1, l, m, ql, qr, T, mx);
}
};
struct DSU {
int n;
vector<int> par, L, R, depth, mn;
DSU() {};
DSU(int N, vector<int> &h) {
n = N;
for (int i = 0; i < n; i++) {
par.push_back(i); L.push_back(i); R.push_back(i); depth.push_back(0);
mn.push_back(h[i]);
}
}
int find(int v) {
if (par[v] == v) return v;
return par[v] = find(par[v]);
}
void unite(int a, int b) {
a = find(a); b = find(b);
if (a != b) {
par[b] = a;
L[a] = min(L[a], L[b]), R[a] = max(R[a], R[b]);
depth[a] = max(depth[a], depth[b]);
mn[a] = min(mn[a], mn[b]);
}
}
};
int r, c;
SegTree row, col;
vi t, h;
DSU dsu;
void initialize(vi T, vi H) {
r = T.size(); c = H.size();
t = T; h = H; dsu = DSU(c, h);
row = SegTree(r, T); col = SegTree(c, H);
return;
}
bool can_reach(int lower, int upper, int s, int d) {
if (s>d) swap(s, d);
int mx = h[col.query(0, 0, c, s, d+1).second];
int lo = 0, hi = r;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (t[row.query(0, 0, r, 0, mid+1).second] > mx) hi = mid;
else lo = mid + 1;
}
int first = lo;
if (first >= r || t[first] <= mx) return false;
auto get_range = [&](int i, int ca, int cb) {
int a = col.left(0, 0, c, 0, ca+1, t[i], true), b = col.right(0, 0, c, cb, c, t[i], true);
a = (a == -1) ? 0 : a+1; b = (b == -1) ? c-1 : b-1;
return make_pair(a, b);
};
s = dsu.find(s), d = dsu.find(d);
while (dsu.depth[s] < first) {
int posx = row.right(0, 0, r, dsu.depth[s], r, dsu.mn[s], false);
if (posx == -1) posx = r-1;
if (posx == dsu.depth[s]) break;
dsu.depth[s] = posx;
int maxy = row.query(0, 0, r, 0, posx+1).second;
auto range = get_range(maxy, dsu.L[s], dsu.R[s]);
int ca = range.first, cb = range.second;
int lef = dsu.L[s], rig = dsu.R[s];
for (int i = ca; i < lef; i++) dsu.unite(s, i);
for (int i = rig; i <= cb; i++) dsu.unite(s, i);
s = dsu.find(s);
}
while (dsu.depth[d] < first) {
int posx = row.right(0, 0, r, dsu.depth[d], r, dsu.mn[d], false);
if (posx == -1) posx = r-1;
if (posx == dsu.depth[d]) break;
dsu.depth[d] = posx;
int maxy = row.query(0, 0, r, 0, posx+1).second;
auto range = get_range(maxy, dsu.L[d], dsu.R[d]);
int ca = range.first, cb = range.second;
int lef = dsu.L[d], rig = dsu.R[d];
for (int i = ca; i < lef; i++) dsu.unite(d, i);
for (int i = rig; i <= cb; i++) dsu.unite(d, i);
d = dsu.find(d);
}
return dsu.find(s) == dsu.find(d);
}
