#include <bits/stdc++.h> #include "obstacles.h" using namespace std; static int N, M; static vector<int> Tval, Hval; static int d; // Segment tree for range maximum static vector<int> seg; // Build segment tree void build(int node, int l, int r) { if (l == r) { seg[node] = Hval[l]; return; } int mid = (l + r) / 2; build(2*node, l, mid); build(2*node+1, mid+1, r); seg[node] = max(seg[2*node], seg[2*node+1]); } // Query max in range [ql..qr] int query(int node, int l, int r, int ql, int qr) { if (r < ql || l > qr) return INT_MIN; if (ql <= l && r <= qr) return seg[node]; int mid = (l + r) / 2; return max(query(2*node, l, mid, ql, qr), query(2*node+1, mid+1, r, ql, qr)); } void initialize(vector<int> T, vector<int> H) { Tval = T; Hval = H; N = Tval.size(); M = Hval.size(); d = Tval[N-1]; // last row temperature seg.assign(4*M, INT_MIN); build(1, 0, M-1); // build segment tree on H } bool can_reach(int L, int R, int S, int D) { int e = min(S, D); int f = max(S, D); int mx = query(1, 0, M-1, e, f); // max humidity in [e..f] return d > mx; // can reach if last row temperature > max humidity in range }