#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using v = vector<T>;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, k, n) for (int i = k; i < n; i++)
struct SegTree {
v<int> tree;
v<int> mx;
SegTree() {}
SegTree(int n) {
tree.assign(4*n, 1e9);
mx.assign(4*n, 0);
}
void build(int p, int l, int r, int i, int x) {
if (l > i || r < i) return;
if (l == r && r == i) {
tree[p] = x;
mx[p] = x;
}
else {
build(2*p, l, (l+r)/2, i, x);
build(2*p+1, (l+r)/2+1, r, i, x);
tree[p] = min(tree[2*p], tree[2*p+1]);
mx[p] = max(mx[2*p], mx[2*p+1]);
}
}
int query(int p, int l, int r, int i, int j) {
if (l > j || r < i) return 0;
if (i <= l && r <= j) return tree[p];
else {
int i1 = query(2*p, l, (l+r)/2, i, j);
int i2 = query(2*p+1, (l+r)/2+1, r, i, j);
return min(i1, i2);
}
}
int maxx(int p, int l, int r, int i, int j) {
if (l > j || r < i) return 0;
if (i <= l && r <= j) return mx[p];
else {
int i1 = maxx(2*p, l, (l+r)/2, i, j);
int i2 = maxx(2*p+1, (l+r)/2+1, r, i, j);
return max(i1, i2);
}
}
};
int N, M;
SegTree stT, stH;
v<int> t, h;
v<int> sig;
void initialize(std::vector<int> T, std::vector<int> H) {
t = T;
h = H;
N = T.size();
M = H.size();
stT = SegTree(N);
stH = SegTree(M);
rep(i, 0, N) {
stT.build(1, 0, N-1, i, T[i]);
}
rep(i, 0, M) {
stH.build(1, 0, M-1, i, H[i]);
}
stack<int> s;
stack<int> idx;
sig.assign(N, -1);
rep(i, 0, N) {
while (s.size() && T[i] > s.top()) {
sig[idx.top()] = i;
idx.pop();
s.pop();
}
s.push(T[i]);
idx.push(i);
}
return;
}
bool salto_valido(int row1, int row2, int l, int r) {
int mnH = stH.query(1, 0, M-1, l, r);
int mnT = stT.query(1, 0, N-1, row1, row2);
if (mnT > mnH) return true;
else return false;
}
pair<int, int> find_range(int S) {
int row = 0;
int l, r;
l = r = S;
int lel = 0, rr = S;
while (lel <= rr) {
int m = (lel+rr)/2;
if (stH.maxx(1, 0, M-1, m, r) < t[0]) {
l = m;
rr = m-1;
}
else lel = m+1;
}
lel = S;
rr = M-1;
while (lel <= rr) {
int m = (lel+rr)/2;
//cout << m << " " << stH.maxx(1, 0, M-1, l, m) << endl;
if (stH.maxx(1, 0, M-1, l, m) < t[0]) {
r = m;
lel = m+1;
}
else rr = m-1;
}
while (sig[row] != -1 && salto_valido(row, sig[row], l, r)) {
row = sig[row];
lel = 0, rr = l;
while (lel <= rr) {
int m = (lel+rr)/2;
if (stH.maxx(1, 0, M-1, m, r) < t[row]) {
l = m;
rr = m-1;
}
else lel = m+1;
}
lel = r;
rr = M-1;
while (lel <= rr) {
int m = (lel+rr)/2;
if (stH.maxx(1, 0, M-1, l, m) < t[row]) {
r = m;
lel = m+1;
}
else rr = m-1;
}
}
return {l, r};
}
bool can_reach(int L, int R, int S, int D) {
int l1, r1;
auto aux = find_range(S);
l1 = aux.first, r1 = aux.second;
int l2, r2;
aux = find_range(D);
l2 = aux.first, r2 = aux.second;
//cout << l1 << " "<< r1 << " " << l2 << " "<< r2 << endl;
if (l1 == l2 && r1 == r2) return true;
else return false;
}
