#include "obstacles.h" #include <bits/stdc++.h> using namespace std; const int MAXLOG = 20; using vi = vector<int>; using pi = pair<int, int>; int r, c; vi t, h; vector<vector<int>> cmin, cmax; int cmp(int x, int y, bool mn) { if (x == -1) return y; else if (y == -1) return x; else if (mn) return h[x] < h[y] ? x : y; else return h[x] > h[y] ? x : y; } void initialize(vi T, vi H) { r = T.size(); c = H.size(); t = T; h = H; cmin.assign(c, vector<int>(MAXLOG, -1)); cmax.assign(c, vector<int>(MAXLOG, -1)); for (int i = 0; i < c; i++) { cmin[i][0] = cmax[i][0] = i; for (int bit = 1; bit < MAXLOG; bit++) { if (i + (1<<(bit))-1 >= c) break; cmin[i][bit] = cmp(cmin[i][bit-1], cmin[i+(1<<(bit-1))][bit-1], true); cmax[i][bit] = cmp(cmax[i][bit-1], cmax[i+(1<<(bit-1))][bit-1], false); } } return; } int query(int l, int r, bool mn) { int ans = -1; for (int i = MAXLOG-1; i >= 0; i--) { if (l + (1<<(i)) > r) continue; ans = cmp(ans, (mn ? cmin : cmax)[l][i], mn); l += (1<<(i)); } return ans; } int extend(int x, int temp, bool right) { for (int i = MAXLOG-1; i >= 0; i--) { int target = right ? (x + (1<<(i))-1) : (x - (1<<(i))+1); if (target < 0 || target >= c) continue; if (right && (cmax[x][i] == -1 || h[cmax[x][i]] >= temp)) continue; if (!right && (cmax[target][i] == -1 || h[cmax[target][i]] >= temp)) continue; x = target; } return x; } bool can_reach(int L, int R, int s, int d) { if (s>d) swap(s, d); int mx = query(s, d+1, false); int first = 0; while (first < r && t[first] <= h[mx]) first++; if (first >= r) return false; auto get_range = [&](int i, int x) { int a = extend(x, t[i], false), b = extend(x, t[i], true); return make_pair(a, b); }; int ra = 0; while (ra < first) { auto range = get_range(ra, s); int best = query(range.first, range.second+1, true); 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 = query(range.first, range.second+1, true); if (t[rb+1] <= h[best]) return false; rb++; d = best; } return true; }