#include "walk.h"
#include <bits/stdc++.h>
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+1;
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) {
return a.y<b.y;
}
bool cmp2(int a,int b) {
return e[a].y>e[b].y;
}
int s,g;
vector<int> c;
int ch,ct;
int sl,sr;
vector<int> lb[N],rb[N];
ll rec[N];
int tr[N];
ll slt[3][4*N],srt[3][4*N];
int lstop,rstop,dir;
ll maxh;
int slp[4*N],srp[4*N];
void modify2(int tree[],int p,int l,int r,int x,int v) {
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==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));
}
int nxt(int tree[],int x) {
if (x>1) return query2(tree,1,1,m2,1,x-1);
else return 0;
}
ll query(ll tree[],int p,int l,int r,int L,int R) {
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) {
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 del(ll tree[],int p,int l,int r,int x) {
modify(tree,p,l,r,x,linf);
}
ll ans=linf;
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 s, int g) {
s++;
g++;
n=X.size(),m=Y.size();
FOR(i,n) x[i]=X[i-1],h[i]=H[i-1];
FOR(i,n) x[i]++;
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);
// 离散化
FOR(i,m) {
if (i==1||e[i].y!=e[i-1].y) rec[++m2]=e[i].y;
tr[i]=m2;
}
// 建筑的左右天桥
FOR(i,m) {
lb[e[i].r].pb(i);
rb[e[i].l].pb(i);
}
// 从高到低排序以便弹出天桥的时候自上而下继承更新
FOR(i,m2) sort(lb[rec[i]].begin(),lb[rec[i]].end(),cmp2);
FOR(i,m2) sort(rb[rec[i]].begin(),rb[rec[i]].end(),cmp2);
// 跨越s横坐标的天桥
FOR(i,m) if (e[i].l<=s&&e[i].r>=s) c.pb(i);
ch=0,ct=c.size()-1;
// 初始化停留在s的扫描线
FOR(i,m2) {
del(slt[0],1,1,m2,i);
del(slt[1],1,1,m2,i);
del(slt[2],1,1,m2,i);
del(srt[0],1,1,m2,i);
del(srt[1],1,1,m2,i);
del(srt[2],1,1,m2,i);
}
REP(i,ch,ct) if (e[c[i]].y<=h[s]) {
modify(slt[0],1,1,m2,tr[c[i]],e[c[i]].y);
modify(slt[1],1,1,m2,tr[c[i]],e[c[i]].y+e[c[i]].y);
modify(slt[2],1,1,m2,tr[c[i]],e[c[i]].y-e[c[i]].y);
modify(srt[0],1,1,m2,tr[c[i]],e[c[i]].y);
modify(srt[1],1,1,m2,tr[c[i]],e[c[i]].y+e[c[i]].y);
modify(srt[2],1,1,m2,tr[c[i]],e[c[i]].y-e[c[i]].y);
modify2(slp,1,1,m2,tr[c[i]],tr[c[i]]);
modify2(srp,1,1,m2,tr[c[i]],tr[c[i]]);
}
sl=sr=s;
// 扩展扫描矩形
dir=1;
lstop=rstop=0;
while (sl>=1&&sr<=n) {
if (!(lstop&&rstop)) {
if (dir==1) {
if (h[sr]>maxh) {
rstop=1;
dir=2;
continue;
}
// 如果两个天桥首尾相接这里可能有问题，之前天桥的结果被删除了
// 用提前删除lb的点来解决，这样rb的点之后又会加回去
if (sr!=n) for (auto &it:lb[sr]) {
modify2(srp,1,1,m2,tr[it],0);
}
for (auto &it:rb[sr]) {
modify2(srp,1,1,m2,tr[it],tr[it]);
ll v=query(srt[0],1,1,m2,tr[it],tr[it]);
ll v2=query(srt[1],1,1,m2,tr[it],m2)-rec[tr[it]];
ll v3=query(srt[2],1,1,m2,1,tr[it])+rec[tr[it]];
modify(srt[0],1,1,m2,tr[it],min(v,min(v2,v3)));
modify(srt[1],1,1,m2,tr[it],min(v,min(v2,v3))+rec[tr[it]]);
modify(srt[2],1,1,m2,tr[it],min(v,min(v2,v3))-rec[tr[it]]);
}
if (sr!=n) for (auto &it:lb[sr]) {
int nxtp=nxt(srp,tr[it]);
if (nxtp) {
ll v=query(srt[0],1,1,m2,tr[it],tr[it]);
ll v2=query(srt[0],1,1,m2,nxtp,nxtp);
if (v2>v+rec[tr[it]]-rec[nxtp]) {
ll v3=v+rec[tr[it]]-rec[nxtp];
modify(srt[0],1,1,m2,nxtp,v3);
modify(srt[1],1,1,m2,nxtp,v3+rec[nxtp]);
modify(srt[2],1,1,m2,nxtp,v3-rec[nxtp]);
}
}
del(srt[0],1,1,m2,tr[it]);
del(srt[1],1,1,m2,tr[it]);
del(srt[2],1,1,m2,tr[it]);
}
maxh=max(maxh,h[sr]);
while (ch<=ct&&e[c[ch]].y<=h[sr]) ch++;
if (sr<n) sr++;
else {
rstop=1;
dir=2;
}
} else if (dir==2) {
if (h[sl]>maxh) {
lstop=1;
dir=1;
continue;
}
// 如果两个天桥首尾相接这里可能有问题，之前天桥的结果被删除了
// 用提前删除lb的点来解决，这样rb的点之后又会加回去
if (sl!=1) for (auto &it:rb[sl]) {
modify2(slp,1,1,m2,tr[it],0);
}
for (auto &it:lb[sl]) {
modify2(slp,1,1,m2,tr[it],tr[it]);
ll v=query(slt[0],1,1,m2,tr[it],tr[it]);
ll v2=query(slt[1],1,1,m2,tr[it],m2);
ll v3=query(slt[2],1,1,m2,1,tr[it]);
modify(slt[0],1,1,m2,tr[it],min(v,min(v2,v3)));
modify(slt[1],1,1,m2,tr[it],min(v,min(v2,v3))+rec[tr[it]]);
modify(slt[2],1,1,m2,tr[it],min(v,min(v2,v3))-rec[tr[it]]);
}
if (sl!=1) for (auto &it:rb[sl]) {
int nxtp=nxt(slp,tr[it]);
if (nxtp) {
ll v=query(slt[0],1,1,m2,tr[it],tr[it]);
ll v2=query(slt[0],1,1,m2,nxtp,nxtp);
if (v2>v+rec[tr[it]]-rec[nxtp]) {
ll v3=v+rec[tr[it]]-rec[nxtp];
modify(slt[0],1,1,m2,nxtp,v3);
modify(slt[1],1,1,m2,nxtp,v3+rec[nxtp]);
modify(slt[2],1,1,m2,nxtp,v3-rec[nxtp]);
}
}
del(slt[0],1,1,m2,tr[it]);
del(slt[1],1,1,m2,tr[it]);
del(slt[2],1,1,m2,tr[it]);
}
maxh=max(maxh,h[sl]);
while (ch<=ct&&e[c[ch]].y<=h[sl]) ch++;
if (sl>1) sl--;
else {
lstop=1;
dir=1;
}
}
}
if (lstop&&rstop) {
if (h[sr]<=h[sl]) {
while (ch<=ct&&e[c[ch]].y<=h[sr]) {
ll vl=query(slt[2],1,1,m2,1,tr[c[ch]])+e[c[ch]].y+x[s]-x[sl];
ll vr=query(srt[2],1,1,m2,1,tr[c[ch]])+e[c[ch]].y+x[sr]-x[s];
modify2(slp,1,1,m2,tr[c[ch]],tr[c[ch]]);
modify2(srp,1,1,m2,tr[c[ch]],tr[c[ch]]);
modify(slt[0],1,1,m2,tr[c[ch]],vl-(x[s]-x[sl]));
modify(slt[1],1,1,m2,tr[c[ch]],vl-(x[s]-x[sl])+rec[tr[c[ch]]]);
modify(slt[2],1,1,m2,tr[c[ch]],vl-(x[s]-x[sl])-rec[tr[c[ch]]]);
modify(srt[0],1,1,m2,tr[c[ch]],vr-(x[sr]-x[s]));
modify(srt[1],1,1,m2,tr[c[ch]],vr-(x[sr]-x[s])+rec[tr[c[ch]]]);
modify(srt[2],1,1,m2,tr[c[ch]],vr-(x[sr]-x[s])-rec[tr[c[ch]]]);
if (vl+x[sr]-x[sl]<vr) {
modify(srt[0],1,1,m2,tr[c[ch]],vl+x[sr]-x[sl]-(x[sr]-x[s]));
modify(srt[1],1,1,m2,tr[c[ch]],vl+x[sr]-x[sl]-(x[sr]-x[s])+rec[tr[c[ch]]]);
modify(srt[2],1,1,m2,tr[c[ch]],vl+x[sr]-x[sl]-(x[sr]-x[s])-rec[tr[c[ch]]]);
} else if (vr+x[sr]-x[sl]<vl) {
modify(slt[0],1,1,m2,tr[c[ch]],vr+x[sr]-x[sl]-(x[s]-x[sl]));
modify(slt[1],1,1,m2,tr[c[ch]],vr+x[sr]-x[sl]-(x[s]-x[sl])+rec[tr[c[ch]]]);
modify(slt[2],1,1,m2,tr[c[ch]],vr+x[sr]-x[sl]-(x[s]-x[sl])-rec[tr[c[ch]]]);
}
ch++;
}
maxh=max(maxh,h[sr]);
rstop=0;
dir=1;
if (!(ch<=ct&&e[c[ch]].y>h[sr]&&e[c[ch]].y<=h[sl])) {
maxh=max(maxh,h[sl]);
lstop=0;
dir=2;
}
} else {
while (ch<=ct&&e[c[ch]].y<=h[sl]) {
ll vl=query(slt[2],1,1,m2,1,tr[c[ch]])+e[c[ch]].y+x[s]-x[sl];
ll vr=query(srt[2],1,1,m2,1,tr[c[ch]])+e[c[ch]].y+x[sr]-x[s];
modify2(slp,1,1,m2,tr[c[ch]],tr[c[ch]]);
modify2(srp,1,1,m2,tr[c[ch]],tr[c[ch]]);
modify(slt[0],1,1,m2,tr[c[ch]],vl-(x[s]-x[sl]));
modify(slt[1],1,1,m2,tr[c[ch]],vl-(x[s]-x[sl])+rec[tr[c[ch]]]);
modify(slt[2],1,1,m2,tr[c[ch]],vl-(x[s]-x[sl])-rec[tr[c[ch]]]);
modify(srt[0],1,1,m2,tr[c[ch]],vr-(x[sr]-x[s]));
modify(srt[1],1,1,m2,tr[c[ch]],vr-(x[sr]-x[s])+rec[tr[c[ch]]]);
modify(srt[2],1,1,m2,tr[c[ch]],vr-(x[sr]-x[s])-rec[tr[c[ch]]]);
if (vl+x[sr]-x[sl]<vr) {
modify(srt[0],1,1,m2,tr[c[ch]],vl+x[sr]-x[sl]-(x[sr]-x[s]));
modify(srt[1],1,1,m2,tr[c[ch]],vl+x[sr]-x[sl]-(x[sr]-x[s])+rec[tr[c[ch]]]);
modify(srt[2],1,1,m2,tr[c[ch]],vl+x[sr]-x[sl]-(x[sr]-x[s])-rec[tr[c[ch]]]);
} else if (vr+x[sr]-x[sl]<vl) {
modify(slt[0],1,1,m2,tr[c[ch]],vr+x[sr]-x[sl]-(x[s]-x[sl]));
modify(slt[1],1,1,m2,tr[c[ch]],vr+x[sr]-x[sl]-(x[s]-x[sl])+rec[tr[c[ch]]]);
modify(slt[2],1,1,m2,tr[c[ch]],vr+x[sr]-x[sl]-(x[s]-x[sl])-rec[tr[c[ch]]]);
}
ch++;
}
maxh=max(maxh,h[sl]);
lstop=0;
dir=2;
if (!(ch<=ct&&e[c[ch]].y>h[sl]&&e[c[ch]].y<=h[sr])) {
maxh=max(maxh,h[sr]);
rstop=0;
dir=1;
}
}
if (sl==1&&sr==n) break;
}
}
int ansp;
FOR(i,m2) {
if (ans>x[sr]-x[s]+query(srt[0],1,1,m2,i,i)+rec[i]) {
ans=x[sr]-x[s]+query(srt[0],1,1,m2,i,i)+rec[i];
ansp=i;
}
}
//cout<<ans<<endl;
return ans;
}
Compilation message
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:291:6: warning: variable 'ansp' set but not used [-Wunused-but-set-variable]
291 | int ansp;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
9208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
9208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
