#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
}
