#include "obstacles.h" #include <iostream> #include <cmath> using namespace std; int prnt[200005],cnt[200005];//DSU int fix[200005],maxt[200005],maxt_n[200005], mint[200005],mint_n[200005]; int sparseH[19][200005],sparseA[19][200005],spnomA[19][200005]; struct H{int h,ind;}; bool operator <(H a,H b){ return a.h<b.h; }; bool operator ==(H a,H b){ return a.h==b.h; }; struct Gr{int A,nom;}; vector <Gr> gr; Gr tmp; int find_set(int u){ if (prnt[u]!=u) prnt[u]=find_set(prnt[u]); return prnt[u]; } void union_set(int u,int v){ u=find_set(u); v=find_set(v); if (u!=v) { if (cnt[v]>cnt[u]) swap(u,v); cnt[u]+=cnt[v]; prnt[v]=u; } } int getmaxH(int a, int b){ int len=b-a+1, k=(int)log2(len-0.1); return max(sparseH[k][a],sparseH[k][b+1-(1<<k)]); } int getnomA(int a, int b){ int len=b-a+1, k=(int)log2(len-0.1); int nom=spnomA[k][b+1-(1<<k)]; if (sparseA[k][a]>sparseA[k][b+1-(1<<k)]) nom=spnomA[k][a]; return nom; } void initialize(std::vector<int> T, std::vector<int> H) { int n=T.size(),m=H.size(); for (int i=0;i<m;i++) { prnt[i]=i; cnt[i]=1; //DSU init if (H[i]<T[0]) fix[i]=1;//empty sparseA[0][i]=-1; sparseH[0][i]=H[i]; spnomA[0][i]=i; } maxt[0]=T[0],maxt_n[0]=0; mint[0]=T[0],mint_n[0]=0; for (int i=1;i<n;i++){ //pref max,min of T maxt[i]=maxt[i-1],maxt_n[i]=maxt_n[i-1]; if (T[i]>maxt[i-1]) maxt[i]=T[i],maxt_n[i]=i; mint[i]=mint[i-1],mint_n[i]=mint_n[i-1]; if (T[i]<mint[i-1]) mint[i]=T[i],mint_n[i]=i; } //+ //***************** 1 ***************** int nmin,hmin; if (fix[0]==1) nmin=0,hmin=H[0]; for (int i=1;i<=m;i++) if (fix[i]==1){ if (fix[i-1]==1) { union_set(i,i-1); if (H[i]<hmin) hmin=H[i],nmin=i; } else hmin=H[i],nmin=i; } else { // fix[i]==0 if (fix[i-1]){ //****** 2 find area of empty cells ******* //cout<<"*"<<i<<endl; //cout<<"hmin,nmin="<<hmin<<" "<<nmin<<endl; int A=0,B=n-1,C; while (A<B){ C=(A+B+1)/2; if (mint[C]>hmin) A=C; else B=C-1; } //cout<<"A="<<A<<endl; if (A>0) { tmp.A=A, tmp.nom=nmin, gr.push_back(tmp); sparseA[0][nmin]=A; } }//fix[i-1]==1 }//i // cout<<"gr (A,nom):"<<endl; // for (int i=0;i<gr.size();i++) cout<<gr[i].A<<" "<<gr[i].nom<<endl; // cout<<"sparseA[0] :"<<endl; // for (int i=0;i<m;i++) // cout<<sparseA[0][i]<<" "; // cout<<endl; //+ //****** Make spase max tables ******* int k=log2(m-0.1); for (int i=1;i<=k;i++){ int len=1<<i,len2=len>>1; for (int j=0;j+len<=m;j++) { sparseH[i][j]=max(sparseH[i-1][j],sparseH[i-1][j+len2]); sparseA[i][j]=sparseA[i-1][j+len2]; spnomA[i][j]=spnomA[i-1][j+len2]; if (sparseA[i-1][j]>sparseA[i-1][j+len/2]){ sparseA[i][j]=sparseA[i-1][j]; spnomA[i][j]=spnomA[i-1][j]; } }//j }//i /* cout<<"sparseH: k= "<<k<<endl; for (int i=0;i<=k;i++){ for (int j=0;j<m;j++) cout<<sparseH[i][j]<<" "; cout<<endl; } cout<<endl; cout<<"sparseA: k= "<<k<<endl; for (int i=0;i<=k;i++){ for (int j=0;j<m;j++) cout<<sparseA[i][j]<<" "; cout<<endl; } cout<<endl; for (int i=0;i<=k;i++){ for (int j=0;j<m;j++) cout<<spnomA[i][j]<<" "; cout<<endl; } cout<<"ok"<<endl; */ //+ //********** last part of DSU ************ for (int i=1;i<(int)gr.size();i++){ int temp=gr[i].A, nom=gr[i].nom; int A=0,B=nom,C; //cout<<"Last: nom,temp="<<nom<<" "<<temp<<endl; while (A<B){ C=(A+B)/2; int maxh=getmaxH(C,nom); if (maxh>=temp) A=C+1; else B=C; } int nom2=getnomA(A,nom-1); //cout<<"Last: A,nom2"<<A<<" "<<nom2<<endl; if (sparseA[0][nom2]>=temp) union_set(nom,nom2); }//i return; } bool can_reach(int L, int R, int S, int D) { S=find_set(S); D=find_set(D); return S==D; }