#include <bits/stdc++.h>
#include "obstacles.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define all(v) v.begin(), v.end()
constexpr ll inf = 1ll << 62ll;
mt19937 mt(34056237);
ll _ = 0;
struct segment_tree {
struct node {
pll mn, mx;
};
ll nt, n;
vector<node> tree;
segment_tree() { }
segment_tree(ll n, vector<int> a) : n(n) {
nt = 1;
while (nt < n) nt *= 2;
tree = vector<node>(2*nt, {{inf, 0}, {-inf, 0}});
for (ll i = 0; i < a.size(); i++) {
tree[nt+i] = {{a[i], i}, {a[i], i}};
}
for (ll i = nt-1; i > 0; i--) {
tree[i].mn = min(tree[2*i].mn, tree[2*i+1].mn);
tree[i].mx = max(tree[2*i].mx, tree[2*i+1].mx);
}
}
pll range_min(ll k, ll tl, ll tr, ll l, ll r) {
if (r < tl || l > tr) return {inf, -1};
if (l <= tl && r >= tr) return tree[k].mn;
ll mid = tl + (tr - tl) / 2;
return min(range_min(2*k, tl, mid, l, r), range_min(2*k+1, mid+1, tr, l, r));
}
pll range_min(ll l, ll r) { return range_min(1, 0, nt-1, l, r); }
pll range_max(ll k, ll tl, ll tr, ll l, ll r) {
if (r < tl || l > tr) return {-inf, 0};
if (l <= tl && r >= tr) return tree[k].mx;
ll mid = tl + (tr - tl) / 2;
return max(range_max(2*k, tl, mid, l, r), range_max(2*k+1, mid+1, tr, l, r));
}
pll range_max(ll l, ll r) { return range_max(1, 0, nt-1, l, r); }
ll first_ge(ll k, ll tl, ll tr, ll l, ll v) {
if (l > tr || tree[k].mx.first < v) return n;
ll mid = tl + (tr - tl) / 2;
ll res = first_ge(2*k, tl, mid, l, v);
if (res < n) return res;
return first_ge(2*k+1, mid+1, tr, l, v);
}
ll first_ge(ll l, ll v) { return first_ge(1, 0, nt-1, l, v); }
ll first_le(ll k, ll tl, ll tr, ll l, ll v) {
if (l > tr || tree[k].mn.first > v) return n;
ll mid = tl + (tr - tl) / 2;
ll res = first_le(2*k, tl, mid, l, v);
if (res < n) return res;
return first_le(2*k+1, mid+1, tr, l, v);
}
ll first_le(ll l, ll v) { return first_le(1, 0, nt-1, l, v); }
ll last_ge(ll k, ll tl, ll tr, ll r, ll v) {
if (tl > r || tree[k].mx.first < v) return -1;
ll mid = tl + (tr - tl) / 2;
ll res = last_ge(2*k+1, mid+1, tr, r, v);
if (res >= 0) return res;
return last_ge(2*k, tl, mid, r, v);
}
ll last_ge(ll r, ll v) { return last_ge(1, 0, nt-1, r, v); }
ll last_le(ll k, ll tl, ll tr, ll r, ll v) {
if (tl > r || tree[k].mn.first > v) return -1;
ll mid = tl + (tr - tl) / 2;
ll res = last_le(2*k+1, mid+1, tr, r, v);
if (res >= 0) return res;
return last_le(2*k, tl, mid, r, v);
}
ll last_le(ll r, ll v) { return last_le(1, 0, nt-1, r, v); }
};
vector<int> T, H;
segment_tree tree_T, tree_H;
void initialize(vector<int> _T, vector<int> _H) {
T = _T; H = _H;
ll n = T.size(), m = H.size();
tree_T = segment_tree(n, T);
tree_H = segment_tree(m, H);
}
pll find_best(ll s) {
ll n = T.size(), m = H.size();
auto safe = [&](ll i, ll j) -> bool {
return T[i] > H[j];
};
ll i = 0, j = s;
auto improve_i = [&]() -> bool {
// maximize T
ll mn_i = tree_T.last_le(i, H[j]) + 1;
ll mx_i = tree_T.first_le(i, H[j]) - 1;
return false;
auto [val, pos] = tree_T.range_max(mn_i, mx_i);
if (val <= T[i]) return false;
i = pos;
return true;
};
auto improve_j = [&]() -> bool {
// minimize H
ll mn_j = tree_H.last_ge(j, T[i]) + 1;
ll mx_j = tree_H.first_ge(j, T[i]) - 1;
return false;
auto [val, pos] = tree_H.range_min(mn_j, mx_j);
if (val >= H[j]) return false;
j = pos;
return true;
};
while (true) {
bool improved = false;
improved |= improve_i();
improved |= improve_j();
if (!improved) break;
}
// make unique
for (ll k = i-1; k >= 0; k--) {
//assert(T[k] <= T[i]);
if (T[k] >= T[i]) i = k;
}
for (ll k = j-1; k >= 0; k--) {
//assert(H[k] >= H[j]);
if (H[k] <= H[j]) j = k;
}
return {i, j};
}
bool can_reach(int L, int R, int S, int D) {
pll s = find_best(S);
pll d = find_best(D);
return s == d;
}
#ifdef TEST
#include "grader.cpp"
#endif
