#include "obstacles.h" #include <bits/stdc++.h> //#include <cassert> //#include <cstdio> using namespace std; int n, m; vector <int> t, h; bool group1b = false; vector <int> group1; bool group2b = false; vector <int> group2; bool group3b = false; vector <pair <int, int>> group30; vector <int> group31, group32, group33; void initialize ( vector <int> T, vector <int> H ) { n = T.size(), m = H.size(); t = T, h = H; if ( n == 1 ) { group1b = true; group1.resize( m ); for ( int i = 0; i < m; i++ ) { group1[i] = -1; if ( i != 0 ) { group1[i] = group1[i - 1]; } if ( t[0] <= h[i] ) { group1[i] = i; } } } else if ( n == 3 and t[0] == 2 and t[1] == 1 and t[2] == 3 ) { group30.resize( m ), group31.resize( m ), group32.resize( m ), group33.resize( m ); for ( int i = 0; i < m; i++ ) { group30[i].first = -1; group31[i] = group32[i] = group33[i] = 0; if ( i != 0 ) { group30[i].first = group30[i - 1].first; group31[i] = group31[i - 1]; group32[i] = group32[i - 1]; group33[i] = group33[i - 1]; } if ( h[i] == 0 ) { group30[i].first = i; } else if ( h[i] == 1 ) { group31[i]++; } else if ( h[i] == 2 ) { group32[i]++; } else { group33[i]++; } } for ( int i = m - 1; i >= 0; i-- ) { group30[i].second = -1; if ( i != m - 1 ) { group30[i].second = group30[i + 1].second; } if ( h[i] == 0 ) { group30[i].second = i; } } group3b = true; } else { group2b = true; group2.resize( m ); for ( int i = 0; i < m; i++ ) { group2[i] = -1; if ( i != 0 ) { group2[i] = group2[i - 1]; } if ( t[n - 1] <= h[i] ) { group2[i] = i; } } } return; } bool can_reach ( int L, int R, int s, int d ) { if ( s > d ) { swap ( s, d ); } if ( group1b == true ) { if ( group1[d] >= s ) { return false; } else { return true; } } else if ( group2b == true ) { if ( group2[d] >= s ) { return false; } else { return true; } } else { int k = group32[d] - group32[s] + group33[d] - group33[s]; if ( k == 0 ) { return true; } if ( group30[s].first != -1 and group30[d].first != -1 ) { int l = group30[s].first, r = group30[d].first; k = group31[s] - group31[l] + group31[d] - group31[r]; if ( k >= s - l + d - r ) { k = group33[r] - group33[l]; if ( k <= 0 ) { return true; } } } if ( group30[s].first != -1 and group30[d].second != -1 ) { int l = group30[s].first, r = group30[d].second; k = group31[s] - group31[l] + group31[r] - group31[d]; if ( k >= s - l + r - d ) { if ( l > r ) { k = group33[r] - group33[l]; if ( k <= 0 ) { return true; } } } } if ( group30[s].second != -1 and group30[d].first != -1 ) { int l = group30[s].second, r = group30[d].first; k = group31[l] - group31[s] + group31[d] - group31[r]; if ( k >= l - s + d - r ) { k = group33[r] - group33[l]; if ( k <= 0 ) { return true; } } } if ( group30[s].second != -1 and group30[d].second != -1 ) { int l = group30[s].second, r = group30[d].second; k = group31[l] - group31[s] + group31[r] - group31[d]; if ( k >= l - s + r - d ) { k = group33[r] - group33[l]; if ( k <= 0 ) { return true; } } } } return false; } /*int main() { int N, M; assert(2 == scanf("%d %d", &N, &M)); std::vector<int> T(N), H(M); for (int i = 0; i < N; i++) assert(1 == scanf("%d", &T[i])); for (int i = 0; i < M; i++) assert(1 == scanf("%d", &H[i])); int Q; assert(1 == scanf("%d", &Q)); std::vector<int> L(Q), R(Q), S(Q), D(Q); for (int i = 0; i < Q; i++) assert(4 == scanf("%d %d %d %d", &L[i], &R[i], &S[i], &D[i])); fclose(stdin); std::vector<bool> A(Q); initialize(T, H); for (int i = 0; i < Q; i++) A[i] = can_reach(L[i], R[i], S[i], D[i]); for (int i = 0; i < Q; i++) if (A[i]) printf("1\n"); else printf("0\n"); fclose(stdout); return 0; }*/