#include "obstacles.h" #include <bits/stdc++.h> #define all(x) x.begin(), x.end() using namespace std; int N, M; struct Dsu{ vector<int> v, maxT, minT, maxH, minH; void build() { v.resize(M, 1); } int findrep(int n) { if(v[n] > 0) return n; int x = findrep(-v[n]); v[n] = -x; return x; } void unite(int a, int b) { a = findrep(a); b = findrep(b); if(a == b) return; if(v[a] > v[b]) swap(a, b); v[b] += v[a]; v[a] = -v[b]; } }; vector<int> tmm, tM; void bulid(int v, int l, int r, vector<int> &V) { if(l == r) { tmm[v] = V[l]; tM[v] = V[l]; return; } int m = (l+r)/2; bulid(v*2, l, m, V); bulid(v*2+1, m+1, r, V); tmm[v] = min(tmm[v*2], tmm[v*2+1]); tM[v] = max(tM[v*2], tM[v*2+1]); } int querym(int v, int l, int r, int ql, int qr) { if(ql > qr) return INT_MAX; if(ql == l && qr == r) return tmm[v]; int m = (l+r)/2; return min( querym(v*2, l, m, ql, min(m, qr)), querym(v*2+1, m+1, r, max(m+1, ql), qr) ); } int queryM(int v, int l, int r, int ql, int qr) { if(ql > qr) return -1; if(ql == l && qr == r) return tM[v]; int m = (l+r)/2; return max( queryM(v*2, l, m, ql, min(m, qr)), queryM(v*2+1, m+1, r, max(m+1, ql), qr) ); } vector<int> group; vector<int> lg, rg; map<int, int> mph; //per ogni umidità, la massima T raggiungibile vector<int> HH; void initialize(std::vector<int> T, std::vector<int> H) { N = T.size(); M = H.size(); tmm.resize(M*4+5); tM.resize(M*4+5); bulid(1, 0, M-1, H); //////////////////////////////// group.resize(M, -1); int G = -1; bool status = 0; for(int i=0; i<M; i++) { if(!status && T[0] > H[i]) { G++; group[i] = G; status = 1; lg.push_back(i-1); } else if(T[0] > H[i]) { group[i] = G; } else { if(i > 0 && group[i-1] != -1) rg.push_back(i); status = 0; } } if(status) rg.push_back(M); ////////////////////////////////// //calcolo mpH vector<int> idh(M); iota(all(idh), 0); sort(all(idh), [&](int i, int j){return H[i] > H[j];}); int t = 0; int hight = -1; for(int i: idh) { int h = H[i]; while(t < T.size() && T[t] > h) { t++; hight = max(hight, T[t-1]); } mph[h] = hight; } HH.swap(H); } bool can_reach(int L, int R, int S, int D) { if(D == S) return 1; if(S > D) swap(D, S); L = max(L, lg[group[S]]+1); R = min(R, rg[group[D]]-1); if(group[S] == group[D]) return 1; int gs = group[S], gd = group[D]; int h1 = querym(1, 0, M-1, L, rg[gs]-1); int h2 = querym(1, 0, M-1, lg[gd]+1, R); int h = queryM(1, 0, M-1, L, R); if(mph[h1] > h && mph[h2] > h) return 1; return 0; } #ifdef MARCO 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; } #endif