#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;
}
};
map<pair<int, int>, int> ump;
const int N = 4e5 + 10;
const int M = 2e5 + 10;
const int LOG = 25;
vector<int>T, H;
const int inf = INT32_MAX;
bool vis[N], used[N];
int up[N][LOG], up_l[N][LOG], up_r[N][LOG], depth[N];
int n, m;
int cnt = 0;
int log2_(int x)
{
return int(log2(x));
//return 31 - __builtin_clz(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();
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];
queue<int> cur;
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) / 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)
{
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], in[N], idd[N];
struct dsu_
{
int p[N], sz[N];
int n;
void add(int ind)
{
p[ind] = ind, sz[ind] = 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)
{
return find(a) == find(b);
}
}dsu;
int nt(int x)
{
return x + 1;
}
int pv(int x)
{
if (x == 0)return m;
return x - 1;
}
void find_nxt(int node)
{
if (used[node])return;
used[node] = true;
if (l[node] == 0 && r[node] == m - 1) return;
if (t[node] == n - 1) return;
int nxt_ind = -1;
int l_x = t[node] + 1;
int r_x = n - 1;
int MN = min(H[nt(r[node])], H[pv(l[node])]);
while (l_x <= r_x)
{
int mid = (l_x + r_x) / 2;
if (c_sp.query_mn(t[node] + 1, mid) > H[in[node]])
{
if (c_sp.query_mx(t[node] + 1, mid) > MN)
{
nxt_ind = mid;
r_x = mid - 1;
}
else
{
l_x = mid + 1;
}
}
else
{
r_x = mid - 1;
}
}
if (nxt_ind == -1)
return;
auto P = find_lr(nxt_ind, in[node]);
pair<int, int> key = { nxt_ind, r_sp.query_id_mn(P.first, P.second) };
if (ump.count(key))
{
nxt[node] = ump[key];
dsu.merge(node, nxt[node]);
}
else
{
cnt++;
dsu.add(cnt);
nxt[node] = cnt;
l[cnt] = P.first;
r[cnt] = P.second;
in[cnt] = key.second;
t[cnt] = nxt_ind;
ump[key] = cnt;
//cur.push(cnt);
dsu.merge(node, nxt[node]);
find_nxt(nxt[node]);
}
}
void find_l(int node)
{
int l_x = in[node] + 1, r_x = r[node], ans_l = in[node];
while (l_x <= r_x)
{
int mid = (l_x + r_x) / 2;
if (r_sp.query_mx(mid, r[node]) <
c_sp.query_mn(t[node] + 1, t[nxt[node]]))
{
ans_l = mid;
l_x = mid + 1;
}
else
{
r_x = mid - 1;
}
}
left_most_x[node] = ans_l;
}
void find_r(int node)
{
int l_x = l[node], r_x = in[node] - 1, ans_l = in[node];
while (l_x <= r_x)
{
int mid = (l_x + r_x) / 2;
if (r_sp.query_mx(l[node], mid) <
c_sp.query_mn(t[node] + 1, t[nxt[node]]))
{
ans_l = mid;
r_x = mid - 1;
}
else
{
l_x = mid + 1;
}
}
right_most_x[node] = ans_l;
}
void dfs(int node)
{
vis[node] = true;
up[node][0] = nxt[node];
up_l[node][0] = left_most_x[node];
up_r[node][0] = right_most_x[node];
if (!vis[nxt[node]] && nxt[node])
dfs(nxt[node]);
depth[node] = depth[nxt[node]] + 1;
for (int i = 1; i < LOG; i++)
{
up[node][i] = up[up[node][i - 1]][i - 1];
if (up[node][i] == 0) {
up_l[node][i] = inf;
up_r[node][i] = -1;
}
else
{
up_l[node][i] = min(up_l[node][i - 1], up_l[up[node][i - 1]][i - 1]);
up_r[node][i] = max(up_r[node][i - 1], up_r[up[node][i - 1]][i - 1]);
}
}
}
void initialize(std::vector<int> T, std::vector<int> H)
{
//ump.reserve(N);
n = T.size();
m = H.size();
H.push_back(inf);
c_sp.build_sparse(T);
r_sp.build_sparse(H);
::T = T;
::H = H;
int cnt_f = 0;
for (int i = 0; i < m;)
{
if (is_free(0, i))
{
cnt++;
cnt_f++;
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;
dsu.add(cnt);
}
else i++;
}
while (!cur.empty())
{
int i = cur.front();
cur.pop();
find_nxt(i);
if (nxt[i])
{
find_l(i);
find_r(i);
}
}
assert(cnt <= N);
for (int i = 1; i <= cnt; i++)
{
assert(i > cnt_f && vis[i]);
if (!vis[i] && nxt[i])
dfs(i);
}
}
bool can_reach(int L, int R, int S, int D)
{
if (S > D) swap(S, D);
if (L > R) swap(L, R);
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)];
if (!dsu.ask(cnt1, cnt2))
return false;
if (depth[cnt1] < depth[cnt2])swap(cnt1, cnt2);
int delta = depth[cnt1] - depth[cnt2];
for (int i = 0; i < LOG; i++)
{
if (delta & (1 << i))
{
if (up_l[cnt1][i] > R || up_r[cnt1][i] < L) return false;
cnt1 = up[cnt1][i];
}
}
if (cnt1 == cnt2)
return true;
int mn = inf, mx = -1;
for (int i = LOG - 1; i >= 0; i--)
{
if (up[cnt1][i] != up[cnt2][i])
{
if (up_l[cnt1][i] > R || up_r[cnt1][i] < L) return false;
if (up_l[cnt2][i] > R || up_r[cnt2][i] < L) return false;
cnt1 = up[cnt1][i];
cnt2 = up[cnt2][i];
}
}
assert(up[cnt1][0] == up[cnt2][0]);
if (up_l[cnt1][0] > R || up_r[cnt1][0] < L) return false;
if (up_l[cnt2][0] > R || up_r[cnt2][0] < L) return false;
return true;
}
