#include "obstacles.h"
#include "bits/stdc++.h"
using namespace std;
int const MAXN=2e5+10,LG=19;
int rec[MAXN]={};
bool dead[MAXN]={},done[MAXN]={};
int par[MAXN]={};
int mn[MAXN]={};
vector<int>ch[MAXN]={};
struct spr
{
int tbl[MAXN][LG]={};
void build(vector<int>a)
{
int n=a.size();
for (int i=0;i<n;i++)
tbl[i][0]=a[i];
for (int i=1;(1<<i)<=n;i++)
for (int j=0;j+(1<<i)-1<n;j++)
tbl[j][i]=max(tbl[j][i-1],tbl[j+(1<<(i-1))][i-1]);
}
int get(int l,int r)
{
int lg=log2(r-l+1);
return max(tbl[l][lg],tbl[r+1-(1<<lg)][lg]);
}
};
int root(int n)
{
return (par[n]==n?n:par[n]=root(par[n]));
}
set<pair<int,int>>S;
void merge(int u,int v)
{
u=root(u);
v=root(v);
if (u==v)
return;
ch[u].push_back(v);
S.erase({mn[u],u});
S.erase({mn[v],v});
par[v]=u;
mn[u]=min(mn[u],mn[v]);
S.insert({mn[u],u});
}
vector<int>t,h;
spr mh,mt;
void rem(int u,int k)
{
vector<int>f;
f.push_back(u);
for (int i=0;i<f.size();i++)
{
for (auto j:ch[f[i]])
{
if (!done[j])
f.push_back(j);
}
}
for (auto i:f)
{
done[i]=1;
rec[i]=min(rec[i],k);
}
}
void initialize(vector<int> T, vector<int> H)
{
t=T;
h=H;
int n=t.size(),m=h.size();
mh.build(h);
mt.build(t);
vector<pair<int,int>>vls;
for (int i=0;i<m;i++)
{
rec[i]=n-1,dead[i]=1;
vls.push_back({h[i],i});
par[i]=i;
mn[i]=h[i];
ch[i]={};
}
sort(begin(vls),end(vls));
reverse(begin(vls),end(vls));
for (int i=0;i<n;i++)
{
while (vls.size()&&t[i]>vls.back().first)
{
int ind=vls.back().second;
vls.pop_back();
dead[ind]=0;
S.insert({mn[ind],ind});
if (ind+1<m&&!dead[ind+1])
merge(ind,ind+1);
if (ind-1>=0&&!dead[ind-1])
merge(ind,ind-1);
}
while (S.size()&&(*rbegin(S)).first>=t[i])
{
int z=(*rbegin(S)).second;
rem(z,i-1);
S.erase(*rbegin(S));
}
}
// cerr<<1<<endl;
return;
}
bool can_reach(int L, int R, int S, int D)// 105636 85190
{
if (D<S)
swap(D,S);
int z=mh.get(S,D);
int h=min(rec[S],rec[D]);
int g=mt.get(0,h);
// if (D==105636&&S==85190)
// {
// cout<<rec[S]<<' '<<rec[D]<<endl;
// cout<<z<<' '<<h<<' '<<g<<endl;
// }
if (g>z)
return 1;
return false;
}
