#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]; long long n,bati; 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){ for(int i=0; i<3; i++){ for(int j=0; j<n; j++){ if(T[i]<=H[j])x[i][j]=-1; else x[i][j]=1; } } } 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){ queue<pair<int,int>>q; int l[3][n]; for(int i=0; i<3; i++){ for(int j=0; j<n; j++){ l[i][j]=-1; } } q.push({0,S}); l[0][S]=0; while(q.size()){ pair<int,int>p=q.front(); q.pop(); //x[i+1][j] x[i][j+1] x[i][j-1] x[i-1][j] if(p.first+1<bati){ if(l[p.first+1][p.second]==-1 && x[p.first+1][p.second]!=-1){ q.push({p.first+1,p.second}); l[p.first+1][p.second]=l[p.first][p.second]; } } if(p.first-1>=0){ if(l[p.first-1][p.second]==-1 && x[p.first-1][p.second]!=-1){ q.push({p.first-1,p.second}); l[p.first-1][p.second]=l[p.first][p.second]; } } if(p.second+1<n){ if(l[p.first][p.second+1]==-1 && x[p.first][p.second+1]!=-1){ q.push({p.first,p.second+1}); l[p.first][p.second+1]=l[p.first][p.second]; } } if(p.second-1>=0){ if(l[p.first][p.second-1]==-1 && x[p.first][p.second-1]!=-1){ q.push({p.first,p.second-1}); l[p.first][p.second-1]=l[p.first][p.second]; } } } if(x[0][D]!=-1){ return true; } else return false; } 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; } }