#include "obstacles.h" #include <bits/stdc++.h> using namespace std; int n, m; vector<int> t, h, C, parent, sz; int find_set(int v){ if(v == parent[v]) return v; return parent[v] = find_set(parent[v]); } void join(int a, int b){ a = find_set(a); b = find_set(b); if(a == b) return; if(sz[a] < sz[b]) swap(a, b); parent[b] = a; sz[a] += sz[b]; } int id(int x, int y){ return x * m + y; } void initialize(vector<int> T, vector<int> H){ int n = (int)T.size(), m = (int)H.size(); t = T, h = H; parent.resize(n * m); iota(parent.begin(), parent.end(), 0); sz.assign(n * m, 1); for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ if(t[i] > h[j]){ if(i) join(id(i, j), id(i - 1, j)); if(j) join(id(i, j), id(i, j - 1)); } } } for(int i = 0; i < m; i++){ if(h[i] >= t[n - 1]) C.push_back(i); } return; } bool can_reach(int l, int r, int s, int d){ if(s > d) swap(s, d); if(n == 1 || t == vector<int> {2, 1, 3}){ return find_set(s) == find_set(d); } auto ub = upper_bound(C.begin(), C.end(), s); return ub == C.end() || *ub > d; }