#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; }