#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) { int maxh=st.query(lbj[0][i], i); if (maxh>=downtemp[i]) lbj[0][i]=-1; } if (rbj[0][i]>-1) { int maxh=st.query(i, rbj[0][i]); if (maxh>=downtemp[i]) rbj[0][i]=-1; } } // propogate bjumping for (int i = 1; i <= lg; i++) { for (int j = 0; j < M; j++) { int t=rbj[i-1][j]; if (t>-1) rbj[i][j]=rbj[i-1][t]; t=lbj[i-1][j]; if (t>-1) lbj[i][j]=lbj[i-1][t]; } } 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]; } // 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]; }