This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include <cstdio>
#include <cassert>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define fi first
#define se second
#define pi pair<int,int>
#define mp make_pair
typedef long long ll;
const int inf=0x3f3f3f3f;
const ll linf=1e18;
const int N=100000+10;
const double eps=1e-5;
const int mo=1e9+7;
int n,m,m2;
ll x[N],h[N];
struct bridge {
int l,r;
ll y;
} e[N];
bool cmp(bridge a,bridge b) {
if (a.y==b.y&&a.l!=b.l) return a.l<b.l;
if (a.y==b.y&&a.l==b.l) return a.r<b.r;
return a.y<b.y;
}
bool cmp2(int a,int b) {
if (e[a].y==e[b].y&&e[a].l!=e[b].l) return e[a].l<e[b].l;
if (e[a].y==e[b].y&&e[a].r!=e[b].r) return e[a].r<e[b].r;
return e[a].y>e[b].y;
}
int s,g;
vector<int> c,d;
int ch,ct,dh,dt;
vector<int> lb[N],rb[N];
ll rec[N];
int to[N];
ll slt[3][4*N],srt[3][4*N],glt[3][4*N],grt[3][4*N];
struct state {
int maxh,l,r,lstop,rstop;
} su,gu;
bool turn;// 0表示轮到sr向右移动，1表示轮到gr向右移动
int slp[4*N],srp[4*N],glp[4*N],grp[4*N];
stack<int> b;
vector<int> lbu[N],rbu[N];
ll backup[N];
ll ans=linf;
void modify2(int tree[],int p,int l,int r,int x,int v) {
if (l>r) return;
if (x<l||x>r) return;
if (l==r) {
tree[p]=v;
return;
}
int mid=(l+r)/2;
if (x<=mid) modify2(tree,2*p,l,mid,x,v);
else modify2(tree,2*p+1,mid+1,r,x,v);
tree[p]=max(tree[2*p],tree[2*p+1]);
}
int query2(int tree[],int p,int l,int r,int L,int R) {
if (l>r||L>R) return 0;
if (L<l||R>r) return 0;
if (l==L&&r==R) return tree[p];
int mid=(l+r)/2;
if (R<=mid) return query2(tree,2*p,l,mid,L,R);
else if (L>mid) return query2(tree,2*p+1,mid+1,r,L,R);
else return max(query2(tree,2*p,l,mid,L,mid),query2(tree,2*p+1,mid+1,r,mid+1,R));
}
ll query(ll tree[],int p,int l,int r,int L,int R) {
if (l>r||L>R) return 0;
if (L<l||R>r) return 0;
if (l==L&&r==R) return tree[p];
int mid=(l+r)/2;
if (R<=mid) return query(tree,2*p,l,mid,L,R);
else if (L>mid) return query(tree,2*p+1,mid+1,r,L,R);
else return min(query(tree,2*p,l,mid,L,mid),query(tree,2*p+1,mid+1,r,mid+1,R));
}
void modify(ll tree[],int p,int l,int r,int x,ll v) {
if (l>r) return;
if (x<l||x>r) return;
if (l==r) {
tree[p]=v;
return;
}
int mid=(l+r)/2;
if (x<=mid) modify(tree,2*p,l,mid,x,v);
else modify(tree,2*p+1,mid+1,r,x,v);
tree[p]=min(tree[2*p],tree[2*p+1]);
}
void update(ll tree[][4*N],int p,int l,int r,int x,ll v) {
modify(tree[0],p,l,r,x,v);
if (v!=linf) modify(tree[1],p,l,r,x,v+rec[x]);
else modify(tree[1],p,l,r,x,linf);
if (v!=linf) modify(tree[2],p,l,r,x,v-rec[x]);
else modify(tree[2],p,l,r,x,linf);
}
void del(ll tree[][4*N],int p,int l,int r,int x) {
update(tree,p,l,r,x,linf);
}
int find(ll h) {
int l=1,r=m2;
int mid,ok=0;
while (l<=r) {
mid=(l+r)/2;
if (rec[mid]<=h) {
ok=mid;
l=mid+1;
} else r=mid-1;
}
return ok;
}
int find2(int tree[],ll h) {
int x=find(h);
if (x==0) return 0;
return query2(tree,1,1,m2,1,x);
}
ll add(ll x,ll y) {
if (x==linf||y==linf) return linf;
return x+y;
}
void compute(int x,int o) {
int sl=0,sr=0,gl=0,gr=0;
if (o==0) {
sl=x;
for (auto &it:lbu[sl]) {
int x=find2(slp,h[it]);
int t=find2(slp,h[sl]);
if (x&&t&&x<=t) {
ll v=query(slt[0],1,1,m2,x,x);
ll v2=add(query(slt[1],1,1,m2,x,t),-rec[x]);
if (v2<v) update(slt,1,1,m2,x,v2);
}
}
for (auto &it:lb[sl]) {
modify2(slp,1,1,m2,to[it],to[it]);
ll v=query(slt[0],1,1,m2,to[it],to[it]);
int x=find2(slp,h[sl]);
ll v2=linf;
if (x) v2=add(query(slt[1],1,1,m2,to[it],x),-rec[to[it]]);
ll v3=add(query(slt[2],1,1,m2,1,to[it]),rec[to[it]]);
ll v4=min(v,min(v2,v3));
backup[to[it]]=v4;
}
if (sl!=1) for (auto &it:rb[sl]) {
int x=find2(slp,rec[to[it]]-1);
if (x) {
ll v=query(slt[0],1,1,m2,x,x);
ll v2=add(query(slt[1],1,1,m2,to[it],to[it]),-rec[x]);
if (v2<v) update(slt,1,1,m2,x,v2);
}
modify2(slp,1,1,m2,to[it],0);
del(slt,1,1,m2,to[it]);
}
for (auto &it:lb[sl]) {
modify2(slp,1,1,m2,to[it],to[it]);
ll v4=backup[to[it]];
if (v4!=linf) update(slt,1,1,m2,to[it],v4);
}
} else if (o==1) {
sr=x;
for (auto &it:rbu[sr]) {
int x=find2(srp,h[it]);
int t=find2(srp,h[sr]);
if (x&&t&&x<=t) {
ll v=query(srt[0],1,1,m2,x,x);
ll v2=add(query(srt[1],1,1,m2,x,t),-rec[x]);
if (v2<v) update(srt,1,1,m2,x,v2);
}
}
for (auto &it:rb[sr]) {
modify2(srp,1,1,m2,to[it],to[it]);
ll v=query(srt[0],1,1,m2,to[it],to[it]);
int x=find2(srp,h[sr]);
ll v2=linf;
if (x) v2=add(query(srt[1],1,1,m2,to[it],x),-rec[to[it]]);
ll v3=add(query(srt[2],1,1,m2,1,to[it]),rec[to[it]]);
ll v4=min(v,min(v2,v3));
backup[to[it]]=v4;
}
if (sr!=n) for (auto &it:lb[sr]) {
int x=find2(srp,rec[to[it]]-1);
if (x) {
ll v=query(srt[0],1,1,m2,x,x);
ll v2=add(query(srt[1],1,1,m2,to[it],to[it]),-rec[x]);
if (v2<v) update(srt,1,1,m2,x,v2);
}
modify2(srp,1,1,m2,to[it],0);
del(srt,1,1,m2,to[it]);
}
for (auto &it:rb[sr]) {
modify2(srp,1,1,m2,to[it],to[it]);
ll v4=backup[to[it]];
if (v4!=linf) update(srt,1,1,m2,to[it],v4);
}
} else if (o==2) {
gl=x;
for (auto &it:lbu[gl]) {
int x=find2(glp,h[it]);
int t=find2(glp,h[gl]);
if (x&&t&&x<=t) {
ll v=query(glt[0],1,1,m2,x,x);
ll v2=add(query(glt[1],1,1,m2,x,t),-rec[x]);
if (v2<v) update(glt,1,1,m2,x,v2);
}
}
for (auto &it:lb[gl]) {
modify2(glp,1,1,m2,to[it],to[it]);
ll v=query(glt[0],1,1,m2,to[it],to[it]);
int x=find2(glp,h[gl]);
ll v2=linf;
if (x) v2=add(query(glt[1],1,1,m2,to[it],x),-rec[to[it]]);
ll v3=add(query(glt[2],1,1,m2,1,to[it]),rec[to[it]]);
ll v4=min(v,min(v2,v3));
backup[to[it]]=v4;
}
if (gl!=1) for (auto &it:rb[gl]) {
int x=find2(glp,rec[to[it]]-1);
if (x) {
ll v=query(glt[0],1,1,m2,x,x);
ll v2=add(query(glt[1],1,1,m2,to[it],to[it]),-rec[x]);
if (v2<v) update(glt,1,1,m2,x,v2);
}
modify2(glp,1,1,m2,to[it],0);
del(glt,1,1,m2,to[it]);
}
for (auto &it:lb[gl]) {
modify2(glp,1,1,m2,to[it],to[it]);
ll v4=backup[to[it]];
if (v4!=linf) update(glt,1,1,m2,to[it],v4);
}
} else if (o==3) {
gr=x;
for (auto &it:rbu[gr]) {
int x=find2(grp,h[it]);
int t=find2(grp,h[gr]);
if (x&&t&&x<=t) {
ll v=query(grt[0],1,1,m2,x,x);
ll v2=add(query(grt[1],1,1,m2,x,t),-rec[x]);
if (v2<v) update(grt,1,1,m2,x,v2);
}
}
for (auto &it:rb[gr]) {
modify2(grp,1,1,m2,to[it],to[it]);
ll v=query(grt[0],1,1,m2,to[it],to[it]);
int x=find2(grp,h[gr]);
ll v2=linf;
if (x) v2=add(query(grt[1],1,1,m2,to[it],x),-rec[to[it]]);
ll v3=add(query(grt[2],1,1,m2,1,to[it]),rec[to[it]]);
ll v4=min(v,min(v2,v3));
backup[to[it]]=v4;
}
if (gr!=n) for (auto &it:lb[gr]) {
int x=find2(grp,rec[to[it]]-1);
if (x) {
ll v=query(grt[0],1,1,m2,x,x);
ll v2=add(query(grt[1],1,1,m2,to[it],to[it]),-rec[x]);
if (v2<v) update(grt,1,1,m2,x,v2);
}
modify2(grp,1,1,m2,to[it],0);
del(grt,1,1,m2,to[it]);
}
for (auto &it:rb[gr]) {
modify2(grp,1,1,m2,to[it],to[it]);
ll v4=backup[to[it]];
if (v4!=linf) update(grt,1,1,m2,to[it],v4);
}
}
}
long long min_distance(std::vector<int> X, std::vector<int> H, std::vector<int> L, std::vector<int> R, std::vector<int> Y, int ss, int gg) {
s=ss+1;
g=gg+1;
n=X.size(),m=Y.size();
FOR(i,n) x[i]=X[i-1],h[i]=H[i-1];
FOR(i,m) e[i].l=L[i-1]+1,e[i].r=R[i-1]+1,e[i].y=Y[i-1];
sort(e+1,e+1+m,cmp);
if (s>g) swap(s,g);
// 离散化
FOR(i,m) {
if (i==1||e[i].y!=e[i-1].y) rec[++m2]=e[i].y;
to[i]=m2;
}
// 建筑的左右天桥
FOR(i,m) {
lb[e[i].r].pb(i);
rb[e[i].l].pb(i);
}
// 从高到低排序以便弹出天桥的时候自上而下继承更新
FOR(i,n) sort(lb[i].begin(),lb[i].end(),cmp2);
FOR(i,n) sort(rb[i].begin(),rb[i].end(),cmp2);
// 跨越s横坐标的天桥
FOR(i,m) if (e[i].l<=s&&e[i].r>=s) c.pb(i);
FOR(i,m) if (e[i].l<=g&&e[i].r>=g) d.pb(i);
ch=0,ct=(int)c.size()-1,dh=0,dt=(int)d.size()-1;
// 预处理从建筑i能看到的所有建筑j（从左或者从右）
REP(i,s,n) {
while (!b.empty()&&h[b.top()]<h[i]) b.pop();
if (!b.empty()) {
int x=b.top();
rbu[x].pb(i);
}
b.push(i);
}
while (!b.empty()) b.pop();
for (int i=s;i>=1;i--) {
while (!b.empty()&&h[b.top()]<h[i]) b.pop();
if (!b.empty()) {
int x=b.top();
lbu[x].pb(i);
}
b.push(i);
}
while (!b.empty()) b.pop();
// 初始化停留在s,g的扫描线
FOR(i,m2) {
del(slt,1,1,m2,i);
del(srt,1,1,m2,i);
}
FOR(i,m2) {
del(glt,1,1,m2,i);
del(grt,1,1,m2,i);
}
while (ch<=ct&&e[c[ch]].y<=h[s]) {
int u=to[c[ch]];
update(slt,1,1,m2,u,e[c[ch]].y);
update(srt,1,1,m2,u,e[c[ch]].y);
modify2(slp,1,1,m2,u,u);
modify2(srp,1,1,m2,u,u);
ch++;
}
while (dh<=dt&&e[d[dh]].y<=h[g]) {
int u=to[d[dh]];
update(glt,1,1,m2,u,e[d[dh]].y);
update(grt,1,1,m2,u,e[d[dh]].y);
modify2(glp,1,1,m2,u,u);
modify2(grp,1,1,m2,u,u);
dh++;
}
// 扩展扫描矩形
su.l=s,su.r=s,gu.l=g,gu.r=g;
su.maxh=h[s],gu.maxh=h[g];
while (1) {
if (turn==0) {
if (su.r==n) break;
compute(su.r,1); // 把之前的扫描线更新为新的扫描线作准备
su.r++;
if (su.r>=g) turn=1;
while (h[su.r]>su.maxh) {
while (su.l>=1) {
if (h[su.l]>su.maxh) {
su.maxh=min(h[su.l],h[su.r]);
while (ch<=ct&&e[c[ch]].y<=su.maxh) {
int u=to[c[ch]];
ll vl=add(query(slt[2],1,1,m2,1,u),e[c[ch]].y+x[s]-x[su.l]);
ll vr=add(query(srt[2],1,1,m2,1,u),e[c[ch]].y+x[su.r]-x[s]);
modify2(slp,1,1,m2,u,u);
modify2(srp,1,1,m2,u,u);
if (vl!=linf) update(slt,1,1,m2,u,vl-(x[s]-x[su.l]));
if (vr!=linf) update(srt,1,1,m2,u,vr-(x[su.r]-x[s]));
if (vl!=linf&&vl+x[su.r]-x[su.l]<vr) update(srt,1,1,m2,u,vl+x[su.r]-x[su.l]-(x[su.r]-x[s]));
else if (vr!=linf&&vr+x[su.r]-x[su.l]<vl) update(slt,1,1,m2,u,vr+x[su.r]-x[su.l]-(x[s]-x[su.l]));
ch++;
}
break;
} else {
compute(su.l,0);
if (su.l>1) su.l--;
else {
su.maxh=h[su.r];
break;
}
}
}
}
} else {
ll v1,v2;
v1=v2=linf;
int j=find2(srp,h[su.r]),k;
if (j) {
v1=add(query(srt[1],1,1,m2,1,j),x[su.r]-x[s]);
k=find2(grp,min(rec[j],h[gu.r]));
}
if (k) v2=add(query(grt[2],1,1,m2,1,k),x[gu.r]-x[g]);
ans=min(ans,add(v1,v2));
if (gu.r==n) break;
compute(gu.r,3);
gu.r++;
turn=0;
while (h[gu.r]>gu.maxh) {
while (gu.l>=1) {
if (h[gu.l]>gu.maxh) {
gu.maxh=min(h[gu.l],h[gu.r]);
while (dh<=dt&&e[d[dh]].y<=gu.maxh) {
int u=to[d[dh]];
ll vl=add(query(glt[2],1,1,m2,1,u),e[d[dh]].y+x[g]-x[gu.l]);
ll vr=add(query(grt[2],1,1,m2,1,u),e[d[dh]].y+x[gu.r]-x[g]);
modify2(glp,1,1,m2,u,u);
modify2(grp,1,1,m2,u,u);
if (vl!=linf) update(glt,1,1,m2,u,vl-(x[g]-x[gu.l]));
if (vr!=linf) update(grt,1,1,m2,u,vr-(x[gu.r]-x[g]));
if (vl!=linf&&vl+x[gu.r]-x[gu.l]<vr) update(grt,1,1,m2,u,vl+x[gu.r]-x[gu.l]-(x[gu.r]-x[g]));
else if (vr!=linf&&vr+x[gu.r]-x[gu.l]<vl) update(glt,1,1,m2,u,vr+x[gu.r]-x[gu.l]-(x[g]-x[gu.l]));
dh++;
}
break;
} else {
compute(gu.l,2);
if (gu.l>1) gu.l--;
else {
gu.maxh=h[gu.r];
break;
}
}
}
}
}
}
if (ans==linf) ans=-1;
return ans;
}
Compilation message (stderr)
walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:389:17: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
389 | if (k) v2=add(query(grt[2],1,1,m2,1,k),x[gu.r]-x[g]);
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
