#include "obstacles.h"
#include <bits/stdc++.h>
#ifdef LOCAL
#include "Debug.h"
#else
#define debug(...) 42
#endif
using namespace std;
template<typename T>
struct SparseTable
{
int n;
vector<vector<T>> mat;
SparseTable(const vector<T>& a)
{
n = int(a.size());
int maxLog = 32 - __builtin_clz(n);
mat.resize(maxLog);
mat[0] = a;
for (int j = 1; j < maxLog; j++)
{
mat[j].resize(n - (1 << j) + 1);
for (int i = 0; i <= n - (1 << j); i++)
mat[j][i] = max(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
}
}
T get(int from, int to)
{
if (from > to)
return -1;
assert(0 <= from && from <= to && to <= n - 1);
int lg = 31 - __builtin_clz(to - from + 1);
return max(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
}
};
int n, m;
vector<int> t, h;
vector<int> l, r, minT, maxT;
int isSub2;
SparseTable<int> *table;
void initialize(vector<int> _t, vector<int> _h) {
t = _t; h = _h;
n = size(t); m = size(h);
isSub2 = 1;
for (int i = 0; i + 1 < n; i++)
if (t[i] > t[i + 1])
isSub2 = 0;
table = new SparseTable(h);
l = r = vector<int>(m, -1);
minT = maxT = vector<int>(n);
for (int i = 0; i < n; i++)
{
minT[i] = i ? min(minT[i - 1], t[i]) : t[i];
maxT[i] = i ? max(maxT[i - 1], t[i]) : t[i];
}
vector<int> maxRow(m, -1);
for (int i = 0; i < m; i++)
{
int low = 0, high = m - 1;
while (low <= high)
{
int mid = (low + high) / 2;
if (minT[mid] > h[i])
{
maxRow[i] = mid;
low = mid + 1;
}
else high = mid - 1;
}
}
vector<int> st;
for (int i = 0; i < m; i++)
{
l[i] = i;
while (!empty(st) && h[st.back()] >= h[i])
st.pop_back();
if (!empty(st))
{
int j = st.back();
int row = min(maxRow[i], maxRow[j]);
int maxHBetween = table->get(j + 1, i - 1);
if (maxT[row] > maxHBetween)
l[i] = l[j];
}
st.push_back(i);
}
st.clear();
for (int i = m - 1; i >= 0; i--)
{
r[i] = i;
while (!empty(st) && h[st.back()] >= h[i])
st.pop_back();
if (!empty(st))
r[i] = st.back();
st.push_back(i);
}
}
bool can_reach(int L, int R, int from, int to) {
if (from > to)
swap(from, to);
if (from + 1 == to)
return 1;
int maxH = table->get(from, to);
int row = n, low = 0, high = n - 1;
while (low <= high)
{
int mid = (low + high) / 2;
if (maxT[mid] > maxH)
{
row = mid;
high = mid - 1;
}
else low = mid + 1;
}
if (row == n)
return 0;
return min(h[l[from]], h[r[from]]) < minT[row] && min(h[l[to]], h[r[to]]) < minT[row];
}
