#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
const int inf = 1e9 + 7;
int n, m;
vector<int> t, h;
vector<int> pref;
set<int> s;
set<int> s2;
void initialize(vector<signed> T, vector<signed> H) {
/*for(int i = 0; i < 20; i++) {
n = m = 10;
t.assign(1 + n + 1, 0);
h.assign(1 + m + 1, inf);
for(int i = 1; i <= n; i++) {
t[i] = rand() % 10;
}
for(int i = 1; i <= m; i++) {
h[i] = rand() % 10;
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(t[i] >= h[j]) {
cout << " ";
} else {
cout << "X";
}
}
cout << "\n";
}
cout << "----------\n";
}*/
n = T.size(), m = H.size();
t.assign(1 + n + 1, 0);
h.assign(1 + m + 1, inf);
s.insert(0);
s.insert(m + 1);
for(int i = 1; i <= n; i++) {
t[i] = T[i - 1];
}
s2.insert(m + 2);
for(int i = 1; i <= m; i++) {
h[i] = H[i - 1];
if(h[i] >= 2) {
s.insert(i);
}
if(h[i] == 0) {
s2.insert(i);
}
}
pref.assign(1 + m + 1, 0);
for(int i = 1; i <= m; i++) {
pref[i] = pref[i - 1];
if(h[i] >= t[n]) {
pref[i]++;
}
}
/*for(int x : s) {
cout << x << " ";
}
cout << "\n";
for(int x : s2) {
cout << x << " ";
}
cout << "\n";*/
}
bool can_reach(signed L, signed R, signed S, signed D) {
int a = S + 1, b = D + 1;
if(a > b) {
swap(a, b);
}
if(b <= a + 1) {
return true; // might have to remove !!
}
// REMOVE!!!!!
if(pref[b] != pref[a]) {
return false;
}
if(s.upper_bound(a) == s.upper_bound(b)) {
return true;
}
int x = *(--s.upper_bound(a));
int y = *(s.upper_bound(a));
if(*s2.lower_bound(x) > y) {
return false;
}
x = *(--s.upper_bound(b));
y = *(s.upper_bound(b));
if(*s2.lower_bound(x) > y) {
return false;
}
return true;
}
