#include "obstacles.h"
#include <bits/stdc++.h>
#ifdef LOCAL
#include "Debug.h"
#else
#define debug(...) 42
#endif
using namespace std;
vector<vector<pair<int, int>>> jumpLeft, jumpRight;
vector<pair<int, int>> intervals;
int maxLog;
void initialize(vector<int> t, vector<int> h) {
int n = size(t), m = size(h);
vector<pair<int, int>> incT = {{t[0], 0}};
auto decT = incT;
for (int i = 1; i < n; i++)
{
if (t[i] > incT.back().first)
incT.push_back({t[i], i});
if (t[i] < decT.back().first)
decT.push_back({t[i], i});
}
vector<vector<pair<int, int>>> eventsAt(n + 1);
for (int i = 0; i < m; i++)
if (h[i] < t[0])
{
int low = 0, high = size(decT) - 1, res = -1;
while (low <= high)
{
int mid = (low + high) / 2;
if (h[i] >= decT[mid].first)
{
res = mid;
high = mid - 1;
}
else low = mid + 1;
}
int row = res < 0 ? n - 1 : decT[res].second - 1;
eventsAt[row].push_back({1, i});
}
else
{
int low = 0, high = size(incT) - 1, res = -1;
while (low <= high)
{
int mid = (low + high) / 2;
if (h[i] < incT[mid].first)
{
res = mid;
high = mid - 1;
}
else low = mid + 1;
}
int row = res >= 0 ? incT[res].second : n;
eventsAt[row].push_back({0, i});
}
set<pair<int, int>> active = {{-1, 0}, {m, 0}};
vector<int> l(m), r(m);
intervals.resize(m);
for (int row = n; row >= 0; row--)
{
sort(rbegin(eventsAt[row]), rend(eventsAt[row]));
for (auto [isGood, col] : eventsAt[row])
if (isGood)
{
auto it = active.lower_bound({col, 1});
auto [nextCol, isNextGood] = *it;
auto [prevCol, isPrevGood] = *prev(it);
active.insert({col, 1});
if (isNextGood && isPrevGood)
{
l[col] = prevCol;
r[col] = nextCol;
}
else if (isNextGood) l[col] = r[col] = nextCol;
else if (isPrevGood) l[col] = r[col] = prevCol;
else l[col] = r[col] = col;
intervals[col] = {prevCol, nextCol};
}
else
{
active.insert({col, 0});
l[col] = r[col] = col;
intervals[col] = {col, col};
}
}
maxLog = 32 - __builtin_clz(m);
jumpLeft = jumpRight = vector<vector<pair<int, int>>>(maxLog, vector<pair<int, int>>(m));
for (int i = 0; i < m; i++)
{
jumpLeft[0][i] = {l[i], l[i]};
jumpRight[0][i] = {r[i], r[i]};
}
for (int i = 1; i < maxLog; i++)
for (int j = 0; j < m; j++)
{
auto [jj, bound] = jumpLeft[i - 1][j];
jumpLeft[i][j] = {jumpLeft[i - 1][jj].first, max(jumpLeft[i - 1][jj].second, bound)};
tie (jj, bound) = jumpRight[i - 1][j];
jumpRight[i][j] = {jumpRight[i - 1][jj].first, min(jumpRight[i - 1][jj].second, bound)};
}
}
bool can_reach(int L, int R, int from, int to) {
if (from > to)
swap(from, to);
if (from + 1 == to)
return 1;
int x = from, y = to;
for (int i = maxLog - 1; i >= 0; i--)
{
auto [xx, bound] = jumpRight[i][x];
if (L <= bound && bound <= R)
x = xx;
auto [yy, bound2] = jumpLeft[i][y];
if (L <= bound2 && bound2 <= R)
y = yy;
}
return intervals[x].second >= to && intervals[y].first <= from;
}
