#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
vector<pair<int,int>> interval;
vector<int> l_par, r_par;
vector<vector<pair<int,int> > > l_jump_max, r_jump_min;
int J;
void my_initialize(vector<int> T, vector<int> H){
T.push_back(0);
T.push_back(int(1e9) + 1);
for(int& x : T) x = 2*x-1 - int(1e9);
for(int& x : H) x = 2*x - int(1e9);
vector<pair<int,int> > T_maxs;
vector<pair<int,int> > T_mins;
for(int i = 0; i < (int)T.size(); i++){
if(i == 0 || T[i] > T_maxs.back().first){
T_maxs.push_back({T[i], i});
}
if(i == 0 || T[i] < -T_mins.back().first){
T_mins.push_back({-T[i], i});
}
}
int N = (int)H.size();
vector<tuple<int,int,int>> locs;
for(int i = 0; i < N; i++){
if(T[0] > H[i]){
// good
int v = lower_bound(T_mins.begin(), T_mins.end(), pair<int,int>{-H[i], 0})->second;
locs.push_back({v, 0, i});
} else {
// bad
int v = lower_bound(T_maxs.begin(), T_maxs.end(), pair<int,int>{H[i], 0})->second;
locs.push_back({v, 1, i});
}
}
l_par.resize(N, -1);
r_par.resize(N, -1);
interval.resize(N, {-1, -1});
set<pair<int,int> > active;
active.insert({-1, 1});
active.insert({N, 1});
sort(locs.rbegin(), locs.rend());
for(auto [h, ctype, i] : locs){
if(ctype == 1){
active.insert({i, 1});
l_par[i] = r_par[i] = i;
} else {
auto [it, _] = active.insert({i, 0});
auto [pi, pt] = *prev(it);
auto [ni, nt] = *next(it);
interval[i] = {pi, ni};
if(pt && nt){
l_par[i] = r_par[i] = i;
} else if(pt){
l_par[i] = r_par[i] = ni;
} else if(nt){
l_par[i] = r_par[i] = pi;
} else {
l_par[i] = pi;
r_par[i] = ni;
}
}
}
while((1 << J) < N) J += 1;
l_jump_max.assign(J, vector<pair<int,int>>(N));
r_jump_min.assign(J, vector<pair<int,int>>(N));
for(int i = 0; i < N; i++){
l_jump_max[0][i] = {l_par[i], l_par[i]};
r_jump_min[0][i] = {r_par[i], r_par[i]};
}
for(int j = 1; j < J; j++){
for(int i = 0; i < N; i++){
l_jump_max[j][i] = {l_jump_max[j-1][l_jump_max[j-1][i].first].first,
max(l_jump_max[j-1][i].second, l_jump_max[j-1][l_jump_max[j-1][i].first].second)};
r_jump_min[j][i] = {r_jump_min[j-1][r_jump_min[j-1][i].first].first,
min(r_jump_min[j-1][i].second, r_jump_min[j-1][r_jump_min[j-1][i].first].second)};
}
}
}
bool my_can_reach(int L, int R, int S, int D){
if(S > D) swap(S, D);
int x = S;
for(int j = J-1; j >= 0; j--){
if(r_jump_min[j][x].second >= L){
x = r_jump_min[j][x].first;
}
}
if(interval[x].second < D) return false;
x = D;
for(int j = J-1; j >= 0; j--){
if(l_jump_max[j][x].second <= R){
x = l_jump_max[j][x].first;
}
}
if(interval[x].first > S) return false;
return true;
}
}
void initialize(vector<int> T, vector<int> H){
my_initialize(T, H);
}
bool can_reach(int L, int R, int S, int D){
return my_can_reach(L, R, S, D);
}
