#include "obstacles.h"
#include <bits/stdc++.h>
#include <unordered_map>
#include <chrono>
using namespace std;
using namespace chrono;
#define TIME_LIMIT_SECONDS 0.05
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) {
if (x <= 0) return 0;
return 31 - __builtin_clz(x);
}
struct sparse_table {
int sp_mx[M][LOG];
int sp_mn[M][LOG];
int id_mn[M][LOG];
int id_mx[M][LOG];
void build_sparse(const vector<int>& a) {
int sz = a.size();
for (int i = 0; i < sz; i++) {
sp_mx[i][0] = sp_mn[i][0] = a[i];
id_mx[i][0] = id_mn[i][0] = i;
}
for (int j = 1; j < LOG; j++) {
for (int i = 0; i + (1 << j) <= sz; 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_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];
}
} r_sp;
bool is_free(int i, int j) {
return T[i] > H[j];
}
int l[N], r[N], t[N], in[N], nxt[N], idd[N];
pair<int, int> find_lr(int ind, int S) {
int ansl = S, ansr = S;
int L = 0, R = S;
while (L <= R) {
int mid = (L + R) >> 1;
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) {
int mid = (L + R) >> 1;
if (r_sp.query_mx(S, mid) < T[ind]) {
ansr = mid;
L = mid + 1;
}
else {
R = mid - 1;
}
}
return { ansl, ansr };
}
struct dsu_ {
int p[N], sz[N];
void add(int ind) {
p[ind] = ind;
sz[ind] = 1;
}
int find(int a) {
if (p[a] == a) return a;
return p[a] = find(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);
p[b] = a;
sz[a] += sz[b];
}
bool ask(int a, int b) {
return find(a) == find(b);
}
} dsu;
auto start = steady_clock::now();
bool time_exceeded()
{
return duration<double>(steady_clock::now() - start).count() > TIME_LIMIT_SECONDS;
};
void initialize(vector<int> _T, vector<int> _H) {
auto start = steady_clock::now();
T = _T;
H = _H;
n = T.size();
m = H.size();
r_sp.build_sparse(H);
int cnt = 0;
queue<int> q;
for (int i = 0; i < m;)
{
if (is_free(0, i)) {
cnt++;
q.push(cnt);
auto P = find_lr(0, i);
l[cnt] = P.first;
r[cnt] = P.second;
t[cnt] = 0;
in[cnt] = r_sp.query_id_mn(l[cnt], r[cnt]);
ump[{0, in[cnt]}] = cnt;
idd[in[cnt]] = cnt;
i = r[cnt] + 1;
dsu.add(cnt);
}
else i++;
}
while (!q.empty())
{
int i = q.front(); q.pop();
if (nxt[i]) assert(false);
int ind = in[i];
int cur_mn = T[t[i]];
for (int x = t[i] + 1; x < n; x++) {
cur_mn = min(cur_mn, T[x]);
if (cur_mn <= H[ind]) break;
auto P = find_lr(x, ind);
if (P.first < l[i] || P.second > r[i]) {
int key_in = r_sp.query_id_mn(P.first, P.second);
pair<int, int> key = { x, key_in };
if (ump.count(key)) {
nxt[i] = ump[key];
}
else {
cnt++;
l[cnt] = P.first;
r[cnt] = P.second;
t[cnt] = x;
in[cnt] = key_in;
ump[key] = cnt;
q.push(cnt);
nxt[i] = cnt;
dsu.add(cnt);
}
dsu.merge(i, nxt[i]);
break;
}
}
}
}
bool can_reach(int L, int R, int S, int D)
{
start = steady_clock::now();
if (S > D) swap(S, D);
if (L != 0 || R != m - 1) return false;
auto p1 = find_lr(0, S);
auto p2 = find_lr(0, D);
int c1 = idd[r_sp.query_id_mn(p1.first, p1.second)];
int c2 = idd[r_sp.query_id_mn(p2.first, p2.second)];
if (time_exceeded())assert(false);
return dsu.ask(c1, c2);
}
