#include "obstacles.h" #include <bits/stdc++.h> using namespace std; int prnt[200005], cnt[200005]; // DSU int fixv[200005], maxt[200005], maxt_n[200005], mintt[200005], mint_n[200005]; int sparseH[19][200005], sparseA[19][200005], spnomA[19][200005]; struct Hval { int h, ind; }; bool operator <(Hval a, Hval b){ return a.h < b.h; } bool operator ==(Hval a, Hval b){ return a.h == b.h; } struct Gr { int A, nom; }; vector<Gr> gr; Gr tmp; int find_set(int u){ if (prnt[u] != u) prnt[u] = find_set(prnt[u]); return prnt[u]; } void union_set(int u, int v){ u = find_set(u); v = find_set(v); if (u == v) return; if (cnt[v] > cnt[u]) swap(u, v); cnt[u] += cnt[v]; prnt[v] = u; } int getmaxH(int a, int b){ int len = b - a + 1; if (len == 1) return sparseH[0][a]; int k = log2(len); return max(sparseH[k][a], sparseH[k][b + 1 - (1 << k)]); } int getnomA(int a, int b){ int len = b - a + 1; if (len == 1) return spnomA[0][a]; int k = log2(len); int nom = spnomA[k][b + 1 - (1 << k)]; if (sparseA[k][a] > sparseA[k][b + 1 - (1 << k)]) nom = spnomA[k][a]; return nom; } void initialize(std::vector<int> T, std::vector<int> H) { int n = T.size(), m = H.size(); gr.clear(); for (int i = 0; i < m; i++){ prnt[i] = i; cnt[i] = 1; fixv[i] = (H[i] < T[0] ? 1 : 0); sparseA[0][i] = -1; sparseH[0][i] = H[i]; spnomA[0][i] = i; } // prefix max/min T maxt[0] = T[0]; maxt_n[0] = 0; mintt[0] = T[0]; mint_n[0] = 0; for (int i = 1; i < n; i++){ maxt[i] = maxt[i-1]; maxt_n[i] = maxt_n[i-1]; if (T[i] > maxt[i-1]){ maxt[i] = T[i]; maxt_n[i] = i; } mintt[i] = mintt[i-1]; mint_n[i] = mint_n[i-1]; if (T[i] < mintt[i-1]){ mintt[i] = T[i]; mint_n[i] = i; } } int nmin = -1; int hmin = 1e9 + 5; if (fixv[0]) { nmin = 0; hmin = H[0]; } for (int i = 1; i < m; i++){ if (fixv[i]){ if (fixv[i-1]) { union_set(i, i-1); if (H[i] < hmin) hmin = H[i], nmin = i; } else { hmin = H[i]; nmin = i; } } else { // fixv[i] == 0 if (fixv[i-1] && nmin != -1) { int A = 0, B = n - 1, C; while (A < B){ C = (A + B + 1) / 2; if (mintt[C] > hmin) A = C; else B = C - 1; } if (A > 0){ tmp.A = A; tmp.nom = nmin; gr.push_back(tmp); sparseA[0][nmin] = A; } } } } int k = log2(max(1, m)); for (int lvl = 1; lvl <= k; lvl++){ int len2 = 1 << (lvl - 1); int len = 1 << lvl; for (int j = 0; j + len <= m; j++){ sparseH[lvl][j] = max(sparseH[lvl-1][j], sparseH[lvl-1][j + len2]); sparseA[lvl][j] = sparseA[lvl-1][j + len2]; spnomA[lvl][j] = spnomA[lvl-1][j + len2]; if (sparseA[lvl-1][j] > sparseA[lvl-1][j + len2]){ sparseA[lvl][j] = sparseA[lvl-1][j]; spnomA[lvl][j] = spnomA[lvl-1][j]; } } } for (int i = 0; i < (int)gr.size(); i++){ int Apos = gr[i].A; int nom = gr[i].nom; int temp = T[Apos]; int height = maxt_n[Apos]; // left if (i > 0){ int A = 0, B = nom, C; while (A < B){ C = (A + B) / 2; int maxh = getmaxH(C, nom); if (maxh >= temp) A = C + 1; else B = C; } if (A < nom){ int nom2 = getnomA(A, nom - 1); if (sparseA[0][nom2] >= height) union_set(nom, nom2); } } // right if (i + 1 < (int)gr.size()){ int A = nom, B = m - 1, C; while (A < B){ C = (A + B + 1) / 2; int maxh = getmaxH(nom, C); if (maxh >= temp) B = C - 1; else A = C; } if (A > nom){ int nom2 = getnomA(nom + 1, A); if (sparseA[0][nom2] >= height) union_set(nom, nom2); } } } } bool can_reach(int L, int R, int S, int D) { return find_set(S) == find_set(D); }