#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>> lbj, rbj;
// 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++;
lbj.assign(lg+1, vector<int>(M, -1));
rbj.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]) {
rbj[0][s.top()]=i; s.pop();
} if (!s.empty()) {
if (H[s.top()]==H[i]) lbj[0][i]=lbj[0][s.top()];
else lbj[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 (lbj[0][i]==-1) lbj[0][i]=i;
else {
int maxh=st.query(lbj[0][i], i);
if (maxh>=downtemp[i]) lbj[0][i]=i;
} if (rbj[0][i]==-1) rbj[0][i]=i;
else {
int maxh=st.query(i, rbj[0][i]);
if (maxh>=downtemp[i]) rbj[0][i]=i;
}
}
// propogate bjumping
for (int i = 1; i <= lg; i++) {
for (int j = 0; j < M; j++) {
rbj[i][j]=rbj[i-1][rbj[i-1][j]];
lbj[i][j]=lbj[i-1][lbj[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 left/right and D left/right until T is 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 (rbj[i][s]>-1) s=rbj[i][s];
// else if (lbj[i][s]>-1) s=lbj[i][s];
// if (rbj[i][d]>-1) d=rbj[i][d];
// else if (lbj[i][d]>-1) d=lbj[i][d];
// }
s=lbj[lg][rbj[lg][s]];
d=rbj[lg][lbj[lg][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];
}
