#include "obstacles.h" #include <bits/stdc++.h> using namespace std; vector<int> v, v1, p, s; int n, m; void make (int n) { p.resize(n); s.assign(n, 1); for(int i = 0; i < n; i++) p[i] = i; } int find (int v) { if(v == p[v]) return v; return p[v] = find(p[v]); } void join (int a, int b) { a = find(a); b = find(b); if(a == b) return; if(s[a] < s[b]) swap(a, b); p[b] = a; s[a] += s[b]; } void initialize (vector<int> T, vector<int> H) { n = T.size(); m = H.size(); if (T == vector<int> {2,1,3}) { make(n * m); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { if(T[i] > H[j]) { if(i > 0 && T[i - 1] > H[j]) join(i * m + j, (i - 1) * m + j); if(j > 0 && T[i] > H[j - 1]) join(i * m + j, i * m + (j - 1)); } } } } v1 = T; for(int i = 0; i < m; i++) { if(H[i] >= T[n - 1]) v.push_back(i); } } bool can_reach(int L, int R, int S, int D) { if(v1 == vector<int> {2,1,3}) { return find(S) == find(D); } auto it = upper_bound(v.begin(), v.end(), min(S, D)); if (it != v.end() && *it < max(S, D)) { return false; } return true; }