#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 = 21; vector<int>T, H; 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(); 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]; 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 (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; 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) > H[nt(r[node])] || c_sp.query_mx(t[node] + 1, mid) > H[pv(l[node])]) { 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]; } 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]); } void find_l(int node) { int l_x = l[node], 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], 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 = r[node], 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], t[nxt[node]])) { ans_l = mid; r_x = mid - 1; } else { l_x = mid + 1; } } right_most_x[node] = ans_l; } const int inf = INT32_MAX; void initialize(std::vector<int> T, std::vector<int> H) { n = T.size(); m = H.size(); H.push_back(inf); c_sp.build_sparse(T); r_sp.build_sparse(H); ::T = T; ::H = H; 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; dsu.add(cnt); } else i++; } while (!cur.empty()) { int i = cur.front(); cur.pop(); find_nxt(i); } for (int i = 1; i < cnt; i++) { if (nxt[i]) { find_l(i); find_r(i); } } } bool can_reach(int L, int R, int S, int D) { if (S > D) swap(S, D); 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; int cur1 = cnt1; int mn = inf, mx = -1; while (l[cur1] > S || r[cur1] < D) { if (nxt[cur1]) { mn = min(mn, left_most_x[cur1]); cur1 = nxt[cur1]; } else { break; } } int cur2 = cnt2; while (l[cur2] > S || r[cur2] < D) { if (nxt[cur2]) { mx = max(mx, right_most_x[cur2]); cur2 = nxt[cur2]; } else break; } if (cur1 == cur2 && l[cur1] <= S && r[cur1] >= D && mn >= L && mx <= R) return true; else return false; }