#include "obstacles.h" #include <bits/stdc++.h> using namespace std; const int N=2e5+5; vector<int>k; vector<int>h; int x[3][N]; int ixvi[3][N]; long long n,bati; //const int N=2e5+5; vector<int>v[N]; vector<pair<int,int>>p; void make_set(int w){ p[w].first=w; p[w].second=1; // parent[v]=v; // size[v]=1; } int rec(int w){ if(w!=p[w].first) { //int len=p[w].second; p[w].first=rec(p[w].first); //p[w].second+=len; } return p[w].first; } void gaertianeba(int u,int w){ int k=rec(u); int h=rec(w); if(k!=h){ if(p[k].second>=p[h].second){ //v[k].push_back(h); p[k].second+=p[h].second; p[h].first=k; } else{ //v[h].push_back(k); p[h].second+=p[k].second; p[k].first=h; } } return; } void initialize(vector<int> T, vector<int> H) { n=H.size(); int j=0; bati=T.size(); for(int j=0; j<H.size(); j++){ if(T[0]<=H[j]){ //x[j]=-1; k.push_back(j); } else{ //x[j]=1; } //cout<<x[j]<<" "; //x[j]=a; //j++; } for(int i=0; i<H.size(); i++){ if(T[bati-1]<=H[i]){ h.push_back(i); //x[i]=-1; } } if(bati==3){ p.assign(3*n, {0,0}); for(int i=0; i<3; i++){ for(int j=0; j<n; j++){ x[i][j]=i*n+j; if(T[i]<=H[j]){ ixvi[i][j]=-1; } else ixvi[i][j]=1; } } for(int i=0; i<bati; i++){ for(int j=0; j<n; j++){ make_set(x[i][j]); } } for(int i=0; i<bati; i++){ for(int j=0; j<n; j++){ if(ixvi[i][j]!=-1){ if(i>0){ if(ixvi[i-1][j]!=-1){ gaertianeba(x[i-1][j],x[i][j]); } } if(j>0){ if(ixvi[i][j-1]!=-1){ gaertianeba(x[i][j-1],x[i][j]); } } } } } } return; } bool can_reach(int L, int R, int S, int D) { //L--,R--,S--,D--; if(S>D)swap(S,D); if(bati==1){ auto it=lower_bound(k.begin(),k.end(),S); if(it!=k.end() && *it<D){ return false; } //if(lower_bound(k.begin(),k.end(),S)<D)return 0; else return true; } else if(bati==3){ // for(int i=0; i<bati; i++){ // for(int j=0; j<n; j++){ // make_set(x[i][j]); // } // } // for(int i=0; i<bati; i++){ // for(int j=0; j<n; j++){ // if(ixvi[i][j]!=-1){ // if(i>0){ // if(ixvi[i-1][j]!=-1){ // gaertianeba(x[i-1][j],x[i][j]); // } // } // if(j>0){ // if(ixvi[i][j-1]!=-1){ // gaertianeba(x[i][j-1],x[i][j]); // } // } // } // } // } int s_id=x[0][S]; int d_id=x[0][D]; int k=rec(s_id); int h=rec(d_id); if(k==h){ return true; } else{ return 0; } } else{ auto it=lower_bound(h.begin(),h.end(),S); if(it!=h.end() && *it<D){ return false; } //if(lower_bound(k.begin(),k.end(),S)<D)return 0; else return true; } }