#include "obstacles.h"
#include <bits/stdc++.h>
using namespace std;
vector <int> ch0, ch2, ch;
void initialize(std::vector<int> T, std::vector<int> H)
{
int i, N = T.size(), M = H.size();
for(i = 0; i < M; i++)
{
if(H[i] == 0) ch0.push_back(i);
else if(H[i] == 2) ch2.push_back(i);
else if(H[i] > 2) ch.push_back(i);
}
}
bool can_reach(int L, int R, int S, int D)
{
int l, r, ind0, ind2, ind;
if(S < D)
{
auto it = lower_bound(ch.begin(), ch.end(), S);
ind = it - ch.begin();
if(ind != ch.size() && ch[ind] < D) return false;
auto it0 = lower_bound(ch0.begin(), ch0.end(), S);
auto it2 = lower_bound(ch2.begin(), ch2.end(), S);
ind0 = it0 - ch0.begin();
ind2 = it2 - ch2.begin();
if(ind2 == ch2.size() || ch2[ind2] > D) return true;
if(ind0 != ch0.size() && ch0[ind0] < ch2[ind2]) return true;
auto itf = upper_bound(ch.begin(), ch.end(), S);
auto it0f = upper_bound(ch0.begin(), ch0.end(), S);
auto it2f = upper_bound(ch2.begin(), ch2.end(), S);
ind = itf- ch.begin() - 1;
ind0 = it0f - ch0.begin() - 1;
ind2 = it2f - ch2.begin() - 1;
if(ind == -1 && ind2 == -1)
{
if(ind0 != -1) return true;
}
else if(ind == -1)
{
if(ind != -1 && ch2[ind2] < ch0[ind0]) return true;
}
else if(ind2 == -1)
{
if(ind != -1 && ch[ind] < ch0[ind0]) return true;
}
else if(ind0 != -1 && ch[ind] < ch0[ind0] && ch2[ind2] < ch0[ind0]) return true;
return false;
}
else if(S > D)
{
auto it = upper_bound(ch.begin(), ch.end(), S);
ind = it - ch.begin() - 1;
if(ind != -1 && ch[ind] > D) return false;
auto it0 = upper_bound(ch0.begin(), ch0.end(), S);
auto it2 = upper_bound(ch2.begin(), ch2.end(), S);
ind0 = it0 - ch0.begin() - 1;
ind2 = it2 - ch2.begin() - 1;
if(ch2[ind2] < D) return true;
if(ind0 != -1 && ch0[ind0] > ch2[ind2]) return true;
auto itf = lower_bound(ch.begin(), ch.end(), S);
auto it0f = lower_bound(ch0.begin(), ch0.end(), S);
auto it2f = lower_bound(ch2.begin(), ch2.end(), S);
ind = itf - ch.begin();
ind0 = it0f - ch0.begin();
ind2 = it2f - ch2.begin();
if(ind == ch.size() && ind2 == ch2.size())
{
if(ind0 != ch0.size()) return true;
}
else if(ind == ch.size())
{
if(ind0 != ch0.size() && ch0[ind0] < ch2[ind2]) return true;
}
else if(ind2 == ch2.size())
{
if(ind0 != ch0.size() && ch0[ind0] < ch[ind]) return true;
}
else if(ind0 != ch0.size() && ch0[ind0] < ch[ind] && ch0[ind0] < ch2[ind2]) return true;
return false;
}
else return true;
return 0;
}
