#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> t,h;
int aint[800005];
void build(int nod, int st, int dr)
{
if(st == dr)
{
aint[nod] = h[st];
return;
}
int mij = (st+dr)/2;
build(nod*2,st,mij);
build(nod*2+1,mij+1,dr);
aint[nod] = max(aint[nod*2], aint[nod*2+1]);
}
int qry(int nod, int st, int dr, int le, int ri)
{
if(le > ri)
return -1;
if(le == st && dr == ri)
return aint[nod];
int mij = (st+dr)/2;
return max(qry(nod*2,st,mij,le,min(mij,ri)), qry(nod*2+1,mij+1,dr,max(mij+1,le),ri));
}
int maxl[200005];
int maxpref[200005];
void initialize(std::vector<int> T, std::vector<int> H)
{
t = T;
h = H;
maxpref[0] = t[0];
for(int i=1;i<t.size();i++)
maxpref[i] = max(maxpref[i-1], t[i]);
build(1,0,(int)h.size()-1);
priority_queue<pair<int,int>> pq;
for(int i=0;i<h.size();i++)
{
maxl[i] = 0;
while(maxl[i] + 1 < (int)t.size() && t[maxl[i]+1] > h[i])
maxl[i]++;
maxl[i] = maxpref[maxl[i]];
pq.push({maxl[i], i});
}
while(!pq.empty())
{
auto [cval,i] = pq.top();
pq.pop();
if(maxl[i] != cval)
continue;
for(int v:{i-1,i+1})
{
if(0 <= v && v < (int)h.size() && maxl[v] < maxl[i] && h[v] < maxl[i])
{
maxl[v] = maxl[i];
pq.push({maxl[v], v});
}
}
}
}
bool can_reach(int L, int R, int S, int D)
{
if(S > D)
swap(S, D);
/*int maxh = 0;
for(int i=S;i<=D;i++)
maxh = max(maxh, h[i]);*/
int maxh = qry(1,0,(int)h.size()-1,S,D);
return (maxl[S] > maxh && maxl[D] > maxh);
}
