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