#include "obstacles.h" #include <bits/stdc++.h> using namespace std; const int N = 2e5 + 10; const int LOG = 21; vector<int>T, H; int n, m; int sp[N][LOG]; void build_sparse() { for (int i = 0; i < m; i++) sp[i][0] = H[i]; for (int i = 0; i < m; i++) { for (int j = 0; j < LOG; j++) { if (i + (1 << j) - 1 >= m)continue; sp[i][j] = max(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]); } } } int query(int l, int r) { int lg = log2(r - l + 1); return max(sp[l][lg], sp[r - (1 << lg) + 1][lg]); } bool is_free(int i, int j) { return T[i] > H[j]; } void initialize(std::vector<int> T, std::vector<int> H) { n = T.size(); m = H.size(); (::T).resize(n); (::H).resize(m); for (int i = 0; i < n; i++)(::T)[i] = T[i]; for (int i = 0; i < m; i++)(::H)[i] = H[i]; build_sparse(); } bool can_reach(int L, int R, int S, int D) { assert(n == 1); if (S > D) swap(S, D); if (T[0] > query(S, D)) return true; else return false; }