#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 // bl=how far are we forced to go left if we are trying to jump right? boundl.assign(lg+1, vector<int>(M)); boundr.assign(lg+1, vector<int>(M)); 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; boundl[0][i]=boundr[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]; } // 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][d]>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]; }