#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXLOG = 18;
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] ? y : x;
}
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-1; i++) {
cmin[i][0] = cmax[i][0] = i+1;
for (int bit = 1; bit < MAXLOG; bit++) {
if (i + (1<<bit) >= 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 = l;
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)) : (x - (1<<i));
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 || h[target] >= 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, 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, 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, true);
if (t[rb+1] <= h[best]) return false;
rb++; d = best;
}
return true;
}
