#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 false; else return true; } 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(ind2 == -1 || ch2[ind2] < D) return true; if(ind0 == -1 || ch0[ind0] < ch2[ind2]) return false; else return true; } else return true; return 0; }