#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;
}
