#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 = 128; const ll E = 7; 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);
}
