#include "obstacles.h"
#include <bits/stdc++.h>
#include <unordered_map>
#include <chrono>
#define TIME_LIMIT_SECONDS 0.5
using namespace std;
using namespace chrono;
struct hash_pair {
size_t operator()(const pair<int, int>& p) const {
return ((size_t)p.first << 32) ^ (size_t)p.second;
}
};
unordered_map<pair<int, int>, int, hash_pair> ump;
const int N = 4e5 + 10;
const int M = 2e5 + 10;
const int LOG = 21;
vector<int>T, H;
int n, m;
int log2_(int x)
{
return 31 - __builtin_clz(x);
//return int(log2(x));
}
struct sparse_table
{
vector<int>a;
int sp_mx[M][LOG];
int sp_mn[M][LOG];
int id_mn[M][LOG];
int id_mx[M][LOG];
void build_sparse(vector<int>H)
{
int m_ = H.size();
a = H;
for (int i = 0; i < m_; i++)
{
sp_mn[i][0] = H[i];
sp_mx[i][0] = H[i];
id_mn[i][0] = i;
id_mx[i][0] = i;
}
for (int j = 1; j < LOG; j++)
{
for (int i = 0; i + (1 << j) <= m_; i++)
{
int mid = i + (1 << (j - 1));
if (sp_mx[i][j - 1] >= sp_mx[mid][j - 1]) {
sp_mx[i][j] = sp_mx[i][j - 1];
id_mx[i][j] = id_mx[i][j - 1];
}
else {
sp_mx[i][j] = sp_mx[mid][j - 1];
id_mx[i][j] = id_mx[mid][j - 1];
}
if (sp_mn[i][j - 1] <= sp_mn[mid][j - 1]) {
sp_mn[i][j] = sp_mn[i][j - 1];
id_mn[i][j] = id_mn[i][j - 1];
}
else {
sp_mn[i][j] = sp_mn[mid][j - 1];
id_mn[i][j] = id_mn[mid][j - 1];
}
}
}
}
int query_mx(int l, int r)
{
int lg = log2_(r - l + 1);
return max(sp_mx[l][lg], sp_mx[r - (1 << lg) + 1][lg]);
}
int query_mn(int l, int r)
{
int lg = log2_(r - l + 1);
return min(sp_mn[l][lg], sp_mn[r - (1 << lg) + 1][lg]);
}
int query_id_mx(int l, int r)
{
int lg = log2_(r - l + 1);
int a = sp_mx[l][lg], b = sp_mx[r - (1 << lg) + 1][lg];
if (a >= b) return id_mx[l][lg];
return id_mx[r - (1 << lg) + 1][lg];
}
int query_id_mn(int l, int r)
{
int lg = log2_(r - l + 1);
int a = sp_mn[l][lg], b = sp_mn[r - (1 << lg) + 1][lg];
if (a <= b) return id_mn[l][lg];
return id_mn[r - (1 << lg) + 1][lg];
}
}c_sp, r_sp;
bool is_free(int i, int j)
{
return T[i] > H[j];
}
int l[N], r[N], right_most_x[N], left_most_x[N], t[N], mn_ind[N];
pair<int, int>find_lr(int ind, int S)
{
int ansl = S, ansr = S;
int L = 0, R = S;
while (L <= R && L >= 0 && R < m)
{
int mid = (L + R) / 2;
if (r_sp.query_mx(mid, S) < T[ind])
{
ansl = mid;
R = mid - 1;
}
else
{
L = mid + 1;
}
}
L = S, R = m - 1;
while (L <= R && L >= 0 && R < m)
{
int mid = (L + R) / 2;
if (r_sp.query_mx(S, mid) < T[ind])
{
ansr = mid;
L = mid + 1;
}
else
{
R = mid - 1;
}
}
return { ansl, ansr };
}
int nxt[N];
int in[N];
int idd[N];
struct dsu_
{
int p[N], sz[N];
int n;
void init(int _n)
{
n = _n;
for (int i = 1; i <= n; i++)
p[i] = i, sz[i] = 1;
}
int find(int a)
{
if (a != p[a])
return p[a] = find(p[a]);
return p[a];
}
void merge(int a, int b)
{
a = find(a), b = find(b);
if (a == b)return;
if (sz[a] < sz[b])swap(a, b);
sz[a] += sz[b];
sz[b] = 0;
p[b] = a;
}
bool ask(int a, int b)
{
a = find(a);
b = find(b);
return (a == b);
}
}dsu;
void initialize(std::vector<int> T, std::vector<int> H)
{
n = T.size();
m = H.size();
c_sp.build_sparse(T);
r_sp.build_sparse(H);
::T = T;
::H = H;
int cnt = 0;
queue<int> cur;
for (int i = 0; i < m;)
{
if (is_free(0, i))
{
cnt++;
cur.push(cnt);
pair<int, int> P = find_lr(0, i);
l[cnt] = P.first;
r[cnt] = P.second;
i = r[cnt] + 1;
t[cnt] = 0;
in[cnt] = r_sp.query_id_mn(l[cnt], r[cnt]);
ump[{t[cnt], in[cnt]}] = cnt;
idd[in[cnt]] = cnt;
}
else i++;
assert(cnt <= N);
}
while (!cur.empty())
{
assert(cnt <= N);
int i = cur.front();
cur.pop();
int ind = in[i];
int cur_mn = T[t[i]];
int x = t[i] + 1;
while (x < n)
{
cur_mn = min(cur_mn, T[x]);
if (cur_mn <= H[ind])
break;
pair<int, int> P = find_lr(x, ind);
if (P.first <= l[i] && P.second >= r[i])
{
if (P.first < l[i] || P.second > r[i])
{
pair<int, int> key = { x, r_sp.query_id_mn(P.first, P.second) };
if (ump.count(key)) {
nxt[i] = ump[key];
}
else {
cnt++;
l[cnt] = P.first;
r[cnt] = P.second;
t[cnt] = x;
ump[key] = cnt;
cur.push(cnt);
nxt[i] = cnt;
in[cnt] = key.second;
}
break;
}
}
assert(cnt <= N);
x++;
}
}
dsu.init(cnt + 10);
for (int i = 1; i < cnt; i++)
if (nxt[i])
dsu.merge(i, nxt[i]);
assert(cnt <= N);
}
bool can_reach(int L, int R, int S, int D)
{
if (S > D) swap(S, D);
if (L != 0 || R != m - 1)
{
return false;
}
pair<int, int>p1 = find_lr(0, S);
pair<int, int>p2 = find_lr(0, D);
int cnt1 = idd[r_sp.query_id_mn(p1.first, p1.second)];
int cnt2 = idd[r_sp.query_id_mn(p2.first, p2.second)];
return dsu.ask(cnt1, cnt2);
}
