#include "obstacles.h" #include <bits/stdc++.h> using namespace std; class DSU { vector<int> parent, size; public: int sets; DSU(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; } }; int dx[4] = {-1,0,1,0}; int dy[4] = {0,-1,0,1}; vector<int> T,H; int n,m; DSU dsu(600001); bool f[600001]; void initialize(vector<int> t, vector<int> h) { n = t.size(); m = h.size(); T=t; H=h; for(int i = 0; i < n; ++i){ for(int j = 0; j < m; ++j){ f[j+m*i] = false; if(T[i] > H[j]) { f[j+m*i] = true; } } } for(int i = 0; i < n; ++i){ for(int j = 0; j < m; ++j){ if(f[j+m*i]){ for(int k = 0; k < 4; ++k){ int A = i+dx[k]; int B = j+dy[k]; if(A >= 0 and B >= 0 and A < n and B < m){ if(f[B+m*A]){ dsu.unite(B+m*A,j+m*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); }