#include "obstacles.h" #include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<ll,ll>; using ti = array<ll,3>; const ll Nm = (1LL<<19); const ll E = 19; const ll INF = 1e18; vector<ll> df; //dsu forward vector<ll> dsz; //dsu current sizes vector<ll> dmin; //store minimum time connected ll gf(ll x) { if (df[x]==x) { return x; } df[x] = gf(df[x]); return df[x]; } void fz(ll a, ll b) { a = gf(a); b = gf(b); if (a==b) { return; } if (dsz[a]>dsz[b]) { swap(a,b); } df[a]=b; dsz[b]+=dsz[a]; dmin[b]=min(dmin[a],dmin[b]); } vector<pii> st; //store max number and min number in range void upd(ll x, ll v) { ll p = x+Nm; st[p]={v,v}; p=p/2; while (p>0) { st[p]={max(st[p].first,v),min(st[p].second,v)}; p=p/2; } } ll v2(ll x) { if (x==0) { return 100; } return __builtin_ctz(x); } pii fzp(pii p1, pii p2) { return {max(p1.first,p2.first),min(p1.second,p2.second)}; } pii qry(ll a, ll b) { if (a>b) { return {-INF,INF}; } ll la = v2(a); ll lb = v2(b+1); if (la<lb) { return fzp(st[(a>>la)+(1LL<<(E-la))],qry(a+(1LL<<la),b)); } else { return fzp(st[(b>>lb)+(1LL<<(E-lb))],qry(a,b-(1LL<<lb))); } } pii bjumpR[Nm][E+1]; //current position, extreme position (leftmost = min) pii bjumpL[Nm][E+1]; //same but rightmost = max ll xt[Nm]; //ll mtv[Nm]; //min t vector: T -> mint vector<ll> mtv(Nm,INF); vector<ll> imtv(Nm,INF); //smallest T to get <= this mint ll fr(ll xl, ll xr, ll Tc) { //get rightmost term in [xl,xr] which has value >=Tc if (qry(xl,xr).first<Tc) { return -1; } ll mmin = xl; ll mmax = xr; while (mmin != mmax) { ll mq = (mmin+mmax+1)/2; if (qry(mq,xr).first>=Tc) { mmin = mq; } else { mmax = mq-1; } } return mmin; } ll fl (ll xl, ll xr, ll Tc) { if (qry(xl,xr).first<Tc) { return -1; } ll mmin = xl; ll mmax = xr; while (mmin != mmax) { ll mq = (mmin+mmax)/2; if (qry(xl,mq).first>=Tc) { mmax = mq; } else { mmin = mq+1; } } return mmin; } void initialize(vector<int> T, vector<int> H) { ll N = T.size(); ll M = H.size(); set<ll> cnums; //compress numbers for (ll x: T) { cnums.insert(x); } for (ll x: H) { cnums.insert(x); } map<ll,ll> cmpn; //compressed numbers ll cind = 0; for (ll x: cnums) { cmpn[x]=cind; cind++; } vector<ll> T1,H1; ll K = M+N+2; //total size of compressed indices for (ll x: T) { T1.push_back(cmpn[x]); } vector<pii> t2v; //Ts sorted in time order for (ll i=0;i<N;i++) { t2v.push_back({cmpn[T[i]],i}); //cout << "t2v push back: "<<cmpn[T[i]]<<","<<i<<"\n"; } sort(t2v.rbegin(),t2v.rend()); queue<pii> q2v; //Ts queued in time order for (pii p0: t2v) { q2v.push(p0); } vector<ll> prcsf[K]; //what Hs do you have to process here for (ll x: H) { H1.push_back(cmpn[x]); } for (ll i=0;i<M;i++) { prcsf[H1[i]].push_back(i); } df = vector<ll>(K+2,-1); dsz = vector<ll>(K+2,1); dmin = vector<ll>(K+2,INF); vector<bool> act(K+2,0); //active? for the dsu st = vector<pii>(2*Nm,{-INF,INF}); //ll mtv[K]; //min t vector: T -> mint //vector<ll> imtv(K+1,INF); //smallest T to get <= this mint for (ll k=(K-1);k>=0;k--) { ll t = K-1-k; //cout << "t="<<t<<"\n"; while (!q2v.empty()) { if ((q2v.front()).first>k) { //activate this row pii p2v = q2v.front(); q2v.pop(); ll x2v = p2v.second; //cout << "activate x2v="<<x2v<<"\n"; df[x2v] = x2v; dsz[x2v] = 1; act[x2v] = 1; dmin[x2v] = t; if (x2v>=1 && act[x2v-1]) { fz(x2v-1,x2v); } if (x2v<(K-1) && act[x2v+1]) { fz(x2v,x2v+1); } } else { break; } } if (act[0]) { //cout << "have activated 0 already at t="<<t<<"\n"; ll mint = dmin[gf(0)]; mtv[t]=mint; imtv[mint]=min(imtv[mint],t); } for (ll x: prcsf[k]) { //process this column upd(x,t); xt[x]=t; } } return; // exit(0); // for (ll k=(K-1);k>=0;k--) { // imtv[k]=min(imtv[k],imtv[k+1]); // } for (ll k=0;k<(K-1);k++) { imtv[k+1]=min(imtv[k],imtv[k+1]); } // for (ll i=0;i<M;i++) { // cout << "xt[i="<<i<<"]="<<xt[i]<<"\n"; // } // for (ll t=0;t<K;t++) { // cout << "mtv[t="<<t<<"]="<<mtv[t]<<"\n"; // cout << "imtv[t="<<t<<"]="<<imtv[t]<<"\n"; // } for (ll x=0;x<M;x++) { ll Tc = xt[x]; ll mtc = mtv[Tc]; if (mtc==INF) { bjumpR[x][0]={x,x}; bjumpL[x][0]={x,x}; continue; } ll Tn = imtv[mtc-1]; //cout << "x,Tc,mtc,Tn="<<x<<","<<Tc<<","<<mtc<<","<<Tn<<"\n"; if (Tn<=K && Tn>=0) { ll xl = fr(0,x-1,Tn); ll xr = fl(x+1,K-1,Tn); if (xl!=-1) { if (qry(xl,x).second<mtc) { xl = -1; } } if (xr!=-1) { if (qry(x,xr).second<mtc) { xr = -1; } } if (xl!=-1 && xr!=-1) { bjumpR[x][0]={xr,x}; bjumpL[x][0]={xl,x}; } else if (xl!=-1 && xr==-1) { bjumpR[x][0]={xl,xl}; bjumpL[x][0]={xl,x}; } else if (xl==-1 && xr!=-1) { bjumpR[x][0]={xr,x}; bjumpL[x][0]={xr,xr}; } else { bjumpR[x][0]={x,x}; bjumpL[x][0]={x,x}; } } else { bjumpR[x][0]={x,x}; bjumpL[x][0]={x,x}; } } // for (ll x=0;x<M;x++) { // cout << "x="<<x<<"\n"; // cout << "bjump l = "<<bjumpL[x][0].first<<","<<bjumpL[x][0].second<<"\n"; // cout << "bjump r = "<<bjumpR[x][0].first<<","<<bjumpR[x][0].second<<"\n"; // } for (ll e=1;e<=E;e++) { for (ll x=0;x<Nm;x++) { pii p1 = bjumpL[x][e-1]; pii p2 = bjumpL[p1.first][e-1]; bjumpL[x][e]={p2.first,max(p1.second,p2.second)}; p1 = bjumpR[x][e-1]; p2 = bjumpR[p1.first][e-1]; bjumpR[x][e]={p2.first,min(p1.second,p2.second)}; } } } bool qryR(ll s, ll l, ll tgt) { //can you get T>=tgt while starting at x=s, staying at x>=l? if (xt[bjumpR[s][E].first]<tgt) { return 0; } if (xt[s]>=tgt) { return 1; } if (bjumpR[s][0].second<l) { return 0; } for (ll e=E;e>=0;e--) { if (bjumpR[s][e].second>=l) { //cout << "bjump e="<<e<<"\n"; //cout << "bjumpR = "<<bjumpR[s][e].first<<","<<bjumpR[s][e].second<<"\n"; s = bjumpR[s][e].first; } if (xt[s]>=tgt) { return 1; } if (bjumpR[s][0].second<l) { return 0; } } return 0; } bool qryL(ll d, ll r, ll tgt) { if (xt[bjumpL[d][E].first]<tgt) { return 0; } if (xt[d]>=tgt) { return 1; } if (bjumpL[d][0].second>r) { return 0; } for (ll e=E;e>=0;e--) { if (bjumpL[d][e].second<=r) { d = bjumpL[d][e].first; } if (xt[d]>=tgt) { return 1; } if (bjumpL[d][0].second>r) { return 0; } } return 0; } bool can_reach(int L, int R, int S, int D) { return 0; ll tgt = imtv[qry(S,D).second]; //cout << "tgt="<<tgt<<"\n"; bool b1 = qryR(S,L,tgt); bool b2 = qryL(D,R,tgt); return (b1 && b2); }