#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[j][i-1]; if (t>-1) rbj[j][i]=rbj[t][i-1]; t=lbj[j][i-1]; if (t>-1) lbj[j][i]=lbj[t][i-1]; } } return; } bool can_reach(int L, int R, int S, int D) { // assume we move left to right if (S>D) swap(S, D); int sl=S, sr=S, dl=D, dr=D; // determine the highest humidity in [S, R] int maxh=st.query(S, 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][sr]>-1) sr=rbj[i][sr]; if (lbj[i][sl]>-1) sl=lbj[i][sl]; if (rbj[i][dr]>-1) dr=rbj[i][dr]; if (lbj[i][dl]>-1) dl=lbj[i][dl]; } // i believe we can just consider sr and dl, not sure return downtemp[sr]>maxh && downtemp[dl]>maxh; }