#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
int prnt[200005], cnt[200005]; // DSU
int fixv[200005], maxt[200005], maxt_n[200005],
mintt[200005], mint_n[200005];
int sparseH[19][200005], sparseA[19][200005], spnomA[19][200005];
struct Hval { int h, ind; };
bool operator <(Hval a, Hval b){ return a.h < b.h; }
bool operator ==(Hval a, Hval b){ return a.h == b.h; }
struct Gr { int A, nom; };
vector<Gr> gr;
Gr tmp;
int find_set(int u){
if (prnt[u] != u) prnt[u] = find_set(prnt[u]);
return prnt[u];
}
void union_set(int u, int v){
u = find_set(u);
v = find_set(v);
if (u == v) return;
if (cnt[v] > cnt[u]) swap(u, v);
cnt[u] += cnt[v];
prnt[v] = u;
}
int getmaxH(int a, int b){
int len = b - a + 1;
if (len == 1) return sparseH[0][a];
int k = log2(len);
return max(sparseH[k][a], sparseH[k][b + 1 - (1 << k)]);
}
int getnomA(int a, int b){
int len = b - a + 1;
if (len == 1) return spnomA[0][a];
int k = log2(len);
int nom = spnomA[k][b + 1 - (1 << k)];
if (sparseA[k][a] > sparseA[k][b + 1 - (1 << k)])
nom = spnomA[k][a];
return nom;
}
void initialize(std::vector<int> T, std::vector<int> H) {
int n = T.size(), m = H.size();
gr.clear();
for (int i = 0; i < m; i++){
prnt[i] = i;
cnt[i] = 1;
fixv[i] = (H[i] < T[0] ? 1 : 0);
sparseA[0][i] = -1;
sparseH[0][i] = H[i];
spnomA[0][i] = i;
}
// prefix max/min T
maxt[0] = T[0]; maxt_n[0] = 0;
mintt[0] = T[0]; mint_n[0] = 0;
for (int i = 1; i < n; i++){
maxt[i] = maxt[i-1];
maxt_n[i] = maxt_n[i-1];
if (T[i] > maxt[i-1]){
maxt[i] = T[i];
maxt_n[i] = i;
}
mintt[i] = mintt[i-1];
mint_n[i] = mint_n[i-1];
if (T[i] < mintt[i-1]){
mintt[i] = T[i];
mint_n[i] = i;
}
}
int nmin = -1;
int hmin = 1e9 + 5;
if (fixv[0]) {
nmin = 0;
hmin = H[0];
}
for (int i = 1; i < m; i++){
if (fixv[i]){
if (fixv[i-1]) {
union_set(i, i-1);
if (H[i] < hmin)
hmin = H[i], nmin = i;
}
else {
hmin = H[i];
nmin = i;
}
}
else { // fixv[i] == 0
if (fixv[i-1] && nmin != -1) {
int A = 0, B = n - 1, C;
while (A < B){
C = (A + B + 1) / 2;
if (mintt[C] > hmin) A = C;
else B = C - 1;
}
if (A > 0){
tmp.A = A;
tmp.nom = nmin;
gr.push_back(tmp);
sparseA[0][nmin] = A;
}
}
}
}
int k = log2(max(1, m));
for (int lvl = 1; lvl <= k; lvl++){
int len2 = 1 << (lvl - 1);
int len = 1 << lvl;
for (int j = 0; j + len <= m; j++){
sparseH[lvl][j] = max(sparseH[lvl-1][j],
sparseH[lvl-1][j + len2]);
sparseA[lvl][j] = sparseA[lvl-1][j + len2];
spnomA[lvl][j] = spnomA[lvl-1][j + len2];
if (sparseA[lvl-1][j] > sparseA[lvl-1][j + len2]){
sparseA[lvl][j] = sparseA[lvl-1][j];
spnomA[lvl][j] = spnomA[lvl-1][j];
}
}
}
for (int i = 0; i < (int)gr.size(); i++){
int Apos = gr[i].A;
int nom = gr[i].nom;
int temp = T[Apos];
int height = maxt_n[Apos];
// left
if (i > 0){
int A = 0, B = nom, C;
while (A < B){
C = (A + B) / 2;
int maxh = getmaxH(C, nom);
if (maxh >= temp) A = C + 1;
else B = C;
}
if (A < nom){
int nom2 = getnomA(A, nom - 1);
if (sparseA[0][nom2] >= height)
union_set(nom, nom2);
}
}
// right
if (i + 1 < (int)gr.size()){
int A = nom, B = m - 1, C;
while (A < B){
C = (A + B + 1) / 2;
int maxh = getmaxH(nom, C);
if (maxh >= temp) B = C - 1;
else A = C;
}
if (A > nom){
int nom2 = getnomA(nom + 1, A);
if (sparseA[0][nom2] >= height)
union_set(nom, nom2);
}
}
}
}
bool can_reach(int L, int R, int S, int D) {
return find_set(S) == find_set(D);
}
