#include <bits/stdc++.h>
#include "obstacles.h"
using namespace std;
static int N, M;
static vector<int> Tval, Hval;
static vector<int> c; // blocked/free
static vector<int> sum; // prefix sum of blocked cells
static vector<int> left; // nearest blocked to the left
static vector<int> right; // nearest blocked to the right
static int d; // temperature of first row
// Segment tree for range minimum query
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] = min(seg[2*node], seg[2*node+1]);
}
// Query min in range [ql..qr]
int query(int node, int l, int r, int ql, int qr) {
if (r < ql || l > qr) return INT_MAX;
if (ql <= l && r <= qr) return seg[node];
int mid = (l + r) / 2;
return min(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[0]; // first row temperature
c.assign(M, 0);
sum.assign(M, 0);
left.assign(M, -1);
right.assign(M, M);
for (int i = 0; i < M; i++)
c[i] = (Hval[i] >= d); // blocked if Hval >= d
// prefix sum of blocked cells
sum[0] = c[0];
for (int i = 1; i < M; i++)
sum[i] = sum[i-1] + c[i];
// nearest blocked to the right
int last = M;
for (int i = M-1; i >= 0; i--) {
if (c[i]) last = i;
else right[i] = last - 1;
}
// nearest blocked to the left
last = -1;
for (int i = 0; i < M; i++) {
if (c[i]) last = i;
else left[i] = last + 1;
}
// build segment tree for Hval
seg.assign(4*M, INT_MAX);
build(1, 0, M-1);
}
bool can_reach(int L, int R, int S, int D) {
if (S > D) swap(S, D);
int min_in_range = query(1, 0, M-1, S, D);
// If temperature > max humidity in the path, llama can go
if (d > min_in_range) return true;
// Also check if prefix sums indicate fully free path
int blocked = sum[D] - (S > 0 ? sum[S-1] : 0);
if (blocked == 0) return true;
return false;
}
