#include <bits/stdc++.h> #include "obstacles.h" using namespace std; static int N, M; static vector<int> Tval, Hval; static vector<int> c; static vector<int> b; static vector<int> sum; static vector<int> l, r; // renamed left/right // Segment trees static vector<int> seg_min, seg_max; // Build segment trees void build_seg_min(int node, int nl, int nr) { if (nl == nr) { seg_min[node] = Hval[nl]; return; } int mid = (nl + nr) / 2; build_seg_min(2*node, nl, mid); build_seg_min(2*node+1, mid+1, nr); seg_min[node] = min(seg_min[2*node], seg_min[2*node+1]); } void build_seg_max(int node, int nl, int nr) { if (nl == nr) { seg_max[node] = Hval[nl]; return; } int mid = (nl + nr) / 2; build_seg_max(2*node, nl, mid); build_seg_max(2*node+1, mid+1, nr); seg_max[node] = max(seg_max[2*node], seg_max[2*node+1]); } int query_min(int node, int nl, int nr, int ql, int qr) { if (qr < nl || nr < ql) return INT_MAX; if (ql <= nl && nr <= qr) return seg_min[node]; int mid = (nl + nr) / 2; return min(query_min(2*node, nl, mid, ql, qr), query_min(2*node+1, mid+1, nr, ql, qr)); } int query_max(int node, int nl, int nr, int ql, int qr) { if (qr < nl || nr < ql) return INT_MIN; if (ql <= nl && nr <= qr) return seg_max[node]; int mid = (nl + nr) / 2; return max(query_max(2*node, nl, mid, ql, qr), query_max(2*node+1, mid+1, nr, ql, qr)); } // Wrappers int call_min(int L, int R) { return query_min(1, 0, M-1, L, R); } int call_max(int L, int R) { return query_max(1, 0, M-1, L, R); } void initialize(vector<int> T, vector<int> H) { Tval = T; Hval = H; N = Tval.size(); M = Hval.size(); int d = Tval[0]; c.assign(M, 0); b.assign(M, -1); sum.assign(M, 0); l.assign(M, 0); r.assign(M, 0); for(int i = 0; i < M; i++) c[i] = (Hval[i] >= d ? 1 : 0); sum[0] = c[0]; for(int i = 1; i < M; i++) sum[i] = sum[i-1] + c[i]; int last = M; for(int i = M-1; i >= 0; i--) { if(c[i] == 1) last = i; r[i] = last-1; } last = -1; for(int i = 0; i < M; i++) { if(c[i] == 1) last = i; l[i] = last+1; } seg_min.assign(4*M, INT_MAX); seg_max.assign(4*M, INT_MIN); build_seg_min(1, 0, M-1); build_seg_max(1, 0, M-1); } bool can_reach(int L, int R, int S, int D) { bool st=false, en=false; if(S > D) swap(S,D); if(call_max(S,D) >= 3) return false; int sad = l[S]; int happy = r[S]; if(call_min(sad, happy) == 0) st = true; sad = l[D]; happy = r[D]; if(call_min(sad, happy) == 0) en = true; if(st && en) return true; if(sum[D]==sum[S-1]) return true; return false; }