#include "obstacles.h" #include <cassert> #include <cstdio> #include <bits/stdc++.h> using namespace std; #define ll long long #define ff first #define ss second #define pb push_back #define endl "\n" int n = 0, m = 0; const int N = 2005; pair<int, int> parent[4][N]; int sz[4][N]; int xs[4] = {1, -1, 0, 0}, ys[4] = {0, 0, 1, -1}; pair<int, int> find_set(pair<int, int> v) { if (v == parent[v.ff][v.ss]) return v; return parent[v.ff][v.ss] = find_set(parent[v.ff][v.ss]); } void make_set(pair<int, int> v) { parent[v.ff][v.ss] = v; sz[v.ff][v.ss] = 1; } void union_sets(pair<int, int> a, pair<int, int> b) { a = find_set(a); b = find_set(b); if (a != b) { if (sz[a.ff][a.ss] < sz[b.ff][b.ss]) swap(a, b); parent[b.ff][b.ss] = a; sz[a.ff][a.ss] += sz[b.ff][b.ss]; } } void initialize(std::vector<int> t, std::vector<int> h){ n = t.size(); m = h.size(); for (int i = 0; i < n; i++){ for (int j = 0; j < m; j++){ make_set({i, j}); } } // t = 2, 1, 3 int j = 0, b = 1, last_i = -1, last_j = -1; for (int i = 0; i < n; i++){ while (j < m && j >= 0){ if (t[i] > h[j]){ for (int k = 0; k < 4; k++){ int i1 = i + xs[k], j1 = j + ys[k]; if (i1 < 0 || i1 >= n || j1 < 0 || j1 >= m || t[i1] <= h[j1]){ continue; } union_sets({i1, j1}, {i, j}); } } j += b; } j -= b; b = -b; } } bool can_reach(int l, int r, int s, int d){ if (find_set({0, s}) == find_set({0, d})){ return 1; } return 0; }