#include "obstacles.h" #include <bits/stdc++.h> using namespace std; class DSU { vector<int> parent, size; public: int sets; DSU(int N = 0) { init(N); } void init(int N){ this->parent.resize(N); this->size.resize(N, 1); for(int i = 0; i < N; i++) this->parent[i] = i; this->sets = N; } int find(int x) { if(this->parent[x] != x) { this->parent[x] = find(this->parent[x]); } return this->parent[x]; } void unite(int x, int y) { int a = find(x); int b = find(y); if (a != b) { if (this->size[a] < this->size[b]) swap(a, b); this->parent[b] = a; this->size[a] += this->size[b]; } } int get_size(int x) { return this->size[find(x)]; } void clear() { int N = this->parent.size(); for (int i = 0; i < N; i++) { this->parent[i] = i; this->size[i] = 1; } this->sets = N; } }; template<typename T> class SegTree { public: int size; vector<T> t; function<T(T, T)> f; T init; SegTree(){} SegTree(int n, T init, function<T(T, T)> f, vector<T> &a): init(init), f(f) { initialize(n, init, f, a); } void initialize(int n, T init_, function<T(T, T)> f_, vector<T> &a) { init = init_; f = f_; size = 1; while (size < n) size <<= 1; t.assign(size << 1, init); build(a, 0, 0, size); } void build(vector<T> &a, int pos, int tl, int tr){ if(tr - tl == 1) { if(tl < a.size()){ t[pos] = a[tl]; } } else { int tm = (tr + tl) >> 1; build(a, 2*pos+1, tl, tm); build(a, 2*pos+2, tm, tr); t[pos] = f(t[2*pos+1],t[2*pos+2]); } } void build(vector<T> &a) { build(a,0,0,size); } void update(int i, T val, int pos, int tl, int tr) { if(tr - tl == 1){ t[pos] = val; return; } int mid = (tl + tr) >> 1; if(i < mid){ update(i,val,2*pos+1,tl,mid); } else { update(i,val,2*pos+2,mid,tr); } t[pos] = f(t[2*pos+1],t[2*pos+2]); } void update(int i, T x) { update(i,x,0,0,size); } T query(int l, int r, int pos, int tl, int tr) { if (r <= tl or tr <= l) return init; if (l <= tl and tr <= r) return t[pos]; int tm = (tl + tr) >> 1; return f(query(l,r,2*pos+1,tl,tm),query(l,r,2*pos+2,tm,tr)); } T query(int l, int r) { return query(l,r,0,0,size); } }; int dx[4] = {-1,0,1,0}; int dy[4] = {0,-1,0,1}; vector<int> T,H; vector<int> down,lt,rt; int n,m; DSU dsu; SegTree<int> st1, st2; void initialize(vector<int> t, vector<int> h) { n = t.size(); m = h.size(); T=t; H=h; dsu.init(m); down.resize(m,0); lt.resize(m,0); rt.resize(m,0); static const int INF = 1e9+1; st1.initialize(n,INF,[&](int x,int y){ return min(x,y); },t); st2.initialize(m,0,[&](int x,int y){ return max(x,y); },h); for(int i = 0; i < m; ++i) { if(t[0] <= h[i]){ down[i] = -1; }else{ int l = 1, r = n; int ans = 0; while (l <= r) { int md = (l + r) >> 1; if (st1.query(0, md) > H[i]) { ans = md; l = md+1; } else { r = md-1; } } down[i] = ans-1; } } for(int i = 0; i < m; ++i){ if(down[i]==-1)continue; int l = i, r = m; int ans = i; while (l <= r) { int md = (l + r) >> 1; if (st2.query(i, md) < T[down[i]]) { ans = md; l = md+1; } else { r = md-1; } } rt[i] = ans-1; } for(int i = 0; i < m; ++i){ if(down[i]==-1)continue; int l = 0, r = i; int ans = i+1; while (l <= r) { int md = (l + r) >> 1; if (st2.query(md, i+1) < T[down[i]]) { ans = md; r = md-1; } else { l = md+1; } } lt[i] = ans; } for(int i = 0; i + 1< m; ++i){ if(down[i] >= 0 and down[i+1] >=0){ dsu.unite(i,i+1); } } SegTree<int> rst(m,0,[&](auto x, auto y){ return max(x,y); },rt); SegTree<int> lst(m,0,[&](auto x, auto y){ return max(x,y); },lt); for(int i = 0; i < m; ++i){ if(down[i] == -1) continue; int curr = down[i]; int idx = i; int l = i+1, r = rt[i]; int ans = i; while (l <= r) { int md = (l + r) >> 1; if (rst.query(i+1, md+1) >= curr) { ans = md; r = md-1; } else { l = md+1; } } if(ans != i){ dsu.unite(ans,i); } } for(int i = 0; i < m; ++i){ if(down[i] == -1) continue; int curr = down[i]; int idx = i; int l = lt[i], r = i-1; int ans = i; while (l <= r) { int md = (l + r) >> 1; if (lst.query(md, i) >= curr) { ans = md; l = md+1; } else { r = md-1; } } if(ans != i){ dsu.unite(ans,i); } } } bool can_reach(int L, int R, int S, int D) { int r1 = dsu.find(S); int r2 = dsu.find(D); return (r1==r2); }