#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<vector<int>> grid;
int n,m; //N=2 for subtask 2
vector<int> DX = {-1,1,0,0};
vector<int> DY = {0,0,-1,1};
class DSU {
public:
int n0;
vector<int> par;
vector<int> size;
DSU(int sz) {
n0 = sz;
size = vector<int>(n0,1);
par=vector<int>(n0); iota(par.begin(), par.end(), (int)0);
}
int find(int u) {
if (u==par[u]) return u;
return par[u] = find(par[u]);
}
void link(int u, int v) {
u = find(u); v = find(v);
if (size[u]<size[v]) swap(u,v);
if (u==v) return; //skip
size[u] += size[v]; size[v] = 0; par[v] = u;
}
};
DSU dsu(0);
void initialize(std::vector<signed> T, std::vector<signed> H) {
//subtask 1, 3
bool fudge = 1;
n = T.size();
m = H.size();
if (fudge) n = 2;
grid = vector<vector<int>>(n, vector<int>(m,0));
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
grid[i][j] = T[i] > H[j];
}
}
for (int j=0; j<m; j++) {
grid[1][j] = T[((int)T.size())-1] > H[j];
}
dsu = DSU(n*m);
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
if (grid[i][j]==0) continue;
for (int d=0; d<4; d++) {
int ni = i + DX[d];
int nj = j + DY[d];
if (0<=ni && ni<n && 0<=nj && nj<m) {
if (grid[ni][nj] == 1) dsu.link(m*i+j, m*ni+nj);
}
}
}
}
return;
}
bool can_reach(signed L, signed R, signed S, signed D) {
assert(L==0);
assert(R==m-1);
//check that (0, S) and (0, D) are in the same component, this is fine because the IDs are 0*m+S, 0*m+D
bool connected = dsu.find(S) == dsu.find(D);
return connected;
}
