#include "obstacles.h" #include <bits/stdc++.h> using namespace std; using vi = vector<int>; using pi = pair<int, int>; struct SegTree { int n; vi arr; vector<pi> st; SegTree() {} SegTree(int N, vi &Arr) { n = N; arr = Arr; st.assign(4*n, {-1, -1}); build(0, 0, n); } pi combine(pi x, pi y) { pi r = {-1, -1}; if (x.first < 0) r.first = y.first; else if (y.first < 0) r.first = x.first; else r.first = arr[x.first] < arr[y.first] ? x.first : y.first; if (x.second < 0) r.second = y.second; else if (y.second < 0) r.second = x.second; else r.second = arr[x.second] > arr[y.second] ? x.second : y.second; return r; } pi build(int i, int l, int r) { if (l+1==r) return st[i] = {l, l}; int m = l + (r- l)/2; return st[i] = combine(build(2*i+1, l, m), build(2*i+2, m, r)); } pi query(int i, int l, int r, int ql, int qr) { if (qr <= l || r <= ql) return {-1, -1}; if (ql <= l && r <= qr) return st[i]; int m = l + (r - l) / 2; return combine(query(2*i+1, l, m, ql, qr), query(2*i+2, m, r, ql, qr)); } }; int r, c; SegTree row, col; vi t, h; void initialize(vi T, vi H) { r = T.size(); c = H.size(); t = T; h = H; row = SegTree(r, T); col = SegTree(c, H); return; } bool can_reach(int L, int R, int s, int d) { if (s>d) swap(s, d); int mx = h[col.query(0, 0, c, s, d+1).second]; int lo = 0, hi = r; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (t[row.query(0, 0, r, 0, mid+1).second] > mx) hi = mid; else lo = mid + 1; } int first = lo; if (first >= r || t[first] <= mx) return false; auto get_range = [&](int i, int x) { int lo1 = 0, hi1 = x; int lo2 = x, hi2 = c; while (lo1 < hi1) { int mid = lo1 + (hi1 - lo1) / 2; if (h[col.query(0, 0, c, mid, x+1).second] < t[i]) hi1 = mid; else lo1 = mid + 1; } while (lo2 < hi2) { int mid = lo2 + (hi2 - lo2) / 2; if (h[col.query(0, 0, c, x, mid+1).second] < t[i]) lo2 = mid+1; else hi2 = mid; } // int a = x, b = x; // while (a > 0 && t[i] > h[a-1]) a--; // while (b < c-1 && t[i] > h[b+1]) b++; return make_pair(lo1, lo2-1); }; int ra = 0; while (ra < first) { auto range = get_range(ra, s); int best = col.query(0, 0, c, range.first, range.second+1).first; if (t[ra+1] <= h[best]) return false; ra++; s = best; } int rb = 0; while (rb < first) { auto range = get_range(rb, d); int best = col.query(0, 0, c, range.first, range.second+1).first; if (t[rb+1] <= h[best]) return false; rb++; d = best; } return true; }