#include "obstacles.h" #include <bits/stdc++.h> #include <unordered_map> #include <chrono> using namespace std; 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; void initialize(vector<int> _T, vector<int> _H) { 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])continue; 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) { 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)]; return dsu.ask(c1, c2); }