#include "obstacles.h"
#include<bits/stdc++.h>
using namespace std;
struct segtree {
int n;
vector<int> st;
void init(vector<int>& v) {
n=v.size();
st.assign(2*n, 0);
for (int i = n; i < 2*n; ++i) st[i]=v[i-n];
for (int i = n-1; i > 0; --i) st[i]=max(st[2*i], st[2*i+1]);
}
int query(int a, int b) {
int s=-1;
a+=n; b+=n;
while (a<=b) {
if (a%2==1) s=max(s, st[a++]);
if (b%2==0) s=max(s, st[b--]);
a/=2; b/=2;
} return s;
}
};
int N, M, lg;
segtree st;
vector<int> premin, premax, downtemp;
vector<vector<int>> plbj, prbj, boundl, boundr; // prefer left/right: not binding
// N M
void initialize(std::vector<int> T, std::vector<int> H) {
// max segtree for humidity
st.init(H);
// prefix max/min for temp
N=T.size();
premin.assign(N, T[0]);
premax.assign(N, T[0]);
for (int i = 1, j = 0; i < N; i++) {
premin[i]=min(premin[i-1], T[i]);
premax[i]=max(premax[i-1], T[i]);
}
// minimum temp you can get by going only down: for blift later
M=H.size();
downtemp.assign(M, 0);
for (int i = 0; i < M; i++) {
int l=0, r=N-1;
while (l<r) {
int mid=(l+r)/2;
if (premin[mid]<=H[i]) r=mid;
else l=mid+1;
} downtemp[i]=premax[r];
}
// we need to find the 0 case for the blifting -- monotone stack
lg=0;
while (M>(1<<lg)) lg++;
plbj.assign(lg+1, vector<int>(M, -1));
prbj.assign(lg+1, vector<int>(M, -1));
stack<int> s;
for (int i = 0; i < M; i++) {
while (!s.empty() && H[s.top()]>H[i]) {
prbj[0][s.top()]=i; s.pop();
} if (!s.empty()) {
if (H[s.top()]==H[i]) plbj[0][i]=plbj[0][s.top()];
else plbj[0][i]=s.top();
} s.push(i);
}
// after monotone stack check if we can actually reach that point, -1 means we cant
for (int i = 0; i < M; i++) {
if (plbj[0][i]==-1 || st.query(plbj[0][i], i)>=downtemp[i]) plbj[0][i]=i;
if (prbj[0][i]==-1 || st.query(i, prbj[0][i])>=downtemp[i]) prbj[0][i]=i;
if (plbj[0][i]==i && prbj[0][i]>i) plbj[0][i]=prbj[0][i], boundr[0][i]=prbj[0][i];
if (prbj[0][i]==i && plbj[0][i]<i) prbj[0][i]=plbj[0][i], boundl[0][i]=plbj[0][i];
}
// bl=how far are we forced to go left if we are trying to jump right?
// propogate bjumping and manage boundary
for (int i = 1; i <= lg; i++) {
for (int j = 0; j < M; j++) {
prbj[i][j]=prbj[i-1][prbj[i-1][j]];
plbj[i][j]=plbj[i-1][plbj[i-1][j]];
boundl[i][j]=min(boundl[i-1][j], boundl[i-1][prbj[i-1][j]]);
boundr[i][j]=max(boundr[i-1][j], boundr[i-1][plbj[i-1][j]]);
}
}
return;
}
bool can_reach(int L, int R, int S, int D) {
if (S>D) swap(S, D);
int s=S, d=D;
// blift S right and D left until reachable or until out of bounds
// impl without L,R first because im just checking if this works
for (int i = lg; i >= 0; i--) {
if (boundl[i][s]<L) continue;
s=prbj[i][s];
}
for (int i = lg; i >= 0; i--) {
if (boundr[i][s]>R) continue;
d=plbj[i][d];
}
// cerr << "starting from S we can reach " << s << '\n';
// cerr << "starting from D we can reach " << d<< '\n';
// cerr << "which have maxtemp as follows " << downtemp[s] << ' ' << downtemp[d] << '\n';
return st.query(min(s, D), max(s, D))<downtemp[s] && st.query(min(d, S), max(d, S))<downtemp[d];
}
