#include "walk.h"
#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+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 to[N];
ll slt[3][16*N],srt[3][16*N];
int lstop,rstop,dir;
ll maxh;
int slp[16*N],srp[16*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) {
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));
}
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);
}
int find(int 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[],int h) {
int x=find(h);
if (x==0) return 0;
return query2(tree,1,1,m2,1,x);
}
void print() {
FOR(i,m2) cout<<query(srt[0],1,1,m2,i,i)<<" ";
cout<<endl;
}
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,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;
}
to[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;
// 预处理从建筑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的扫描线
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);
}
while (ch<=ct&&e[c[ch]].y<=h[s]) {
modify(slt[0],1,1,m2,to[c[ch]],e[c[ch]].y);
modify(slt[1],1,1,m2,to[c[ch]],e[c[ch]].y+e[c[ch]].y);
modify(slt[2],1,1,m2,to[c[ch]],e[c[ch]].y-e[c[ch]].y);
modify(srt[0],1,1,m2,to[c[ch]],e[c[ch]].y);
modify(srt[1],1,1,m2,to[c[ch]],e[c[ch]].y+e[c[ch]].y);
modify(srt[2],1,1,m2,to[c[ch]],e[c[ch]].y-e[c[ch]].y);
modify2(slp,1,1,m2,to[c[ch]],to[c[ch]]);
modify2(srp,1,1,m2,to[c[ch]],to[c[ch]]);
ch++;
}
// 扩展扫描矩形
sl=sr=s;
maxh=h[s];
dir=1;
lstop=rstop=0;
int old_sl=0,old_sr=0;
bool flag=0;
while (sl>=1&&sr<=n) {
if (!(lstop&&rstop)) {
if (dir==1) {
if (h[sr]>maxh) {
rstop=1;
dir=2;
continue;
}
// 如果两个天桥首尾相接这里可能有问题，之前天桥的结果被删除了
// 用提前删除lb的点来解决，这样rb的点之后又会加回去
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=query(srt[1],1,1,m2,x,t)-rec[x];
if (v2<v) {
modify(srt[0],1,1,m2,x,v2);
modify(srt[1],1,1,m2,x,v2+rec[x]);
modify(srt[2],1,1,m2,x,v2-rec[x]);
}
}
}
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]);
//ll v2=query(srt[1],1,1,m2,to[it],query2(srp,1,1,m2,1,m2));
int x=find2(srp,h[sr]);
ll v2=linf;
if (x) v2=query(srt[1],1,1,m2,to[it],x);
if (v2!=linf) v2-=rec[to[it]];
ll v3=query(srt[2],1,1,m2,1,to[it]);
if (v3!=linf) v3+=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=query(srt[1],1,1,m2,to[it],to[it])-rec[x];
if (v2<v) {
modify(srt[0],1,1,m2,x,v2);
modify(srt[1],1,1,m2,x,v2+rec[x]);
modify(srt[2],1,1,m2,x,v2-rec[x]);
}
}
modify2(srp,1,1,m2,to[it],0);
del(srt[0],1,1,m2,to[it]);
del(srt[1],1,1,m2,to[it]);
del(srt[2],1,1,m2,to[it]);
}
for (auto &it:rb[sr]) {
ll v4=backup[to[it]];
if (v4!=linf) {
modify(srt[0],1,1,m2,to[it],v4);
modify(srt[1],1,1,m2,to[it],v4+rec[to[it]]);
modify(srt[2],1,1,m2,to[it],v4-rec[to[it]]);
}
}
if (sr<n) sr++;
else {
rstop=1;
dir=2;
}
} else if (dir==2) {
if (h[sl]>maxh) {
lstop=1;
dir=1;
continue;
}
// 如果两个天桥首尾相接这里可能有问题，之前天桥的结果被删除了
// 用提前删除lb的点来解决，这样rb的点之后又会加回去
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=query(slt[1],1,1,m2,x,t)-rec[x];
if (v2<v) {
modify(slt[0],1,1,m2,x,v2);
modify(slt[1],1,1,m2,x,v2+rec[x]);
modify(slt[2],1,1,m2,x,v2-rec[x]);
}
}
}
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]);
//ll v2=query(slt[1],1,1,m2,to[it],query2(slp,1,1,m2,1,m2));
int x=find2(slp,h[sl]);
ll v2=linf;
if (x) v2=query(slt[1],1,1,m2,to[it],x);
if (v2!=linf) v2-=rec[to[it]];
ll v3=query(slt[2],1,1,m2,1,to[it]);
if (v3!=linf) v3+=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=query(slt[1],1,1,m2,to[it],to[it])-rec[x];
if (v2<v) {
modify(slt[0],1,1,m2,x,v2);
modify(slt[1],1,1,m2,x,v2+rec[x]);
modify(slt[2],1,1,m2,x,v2-rec[x]);
}
}
modify2(slp,1,1,m2,to[it],0);
del(slt[0],1,1,m2,to[it]);
del(slt[1],1,1,m2,to[it]);
del(slt[2],1,1,m2,to[it]);
}
for (auto &it:lb[sl]) {
ll v4=backup[to[it]];
if (v4!=linf) {
modify(slt[0],1,1,m2,to[it],v4);
modify(slt[1],1,1,m2,to[it],v4+rec[to[it]]);
modify(slt[2],1,1,m2,to[it],v4-rec[to[it]]);
}
}
if (sl>1) sl--;
else {
lstop=1;
dir=1;
}
}
}
if (lstop&&rstop) {
if (sl==old_sl&&sr==old_sr) {
flag=1;
break;
}
old_sl=sl,old_sr=sr;
if (h[sr]<=h[sl]) {
while (ch<=ct&&e[c[ch]].y<=h[sr]) {
ll vl=query(slt[2],1,1,m2,1,to[c[ch]]);
if (vl!=linf) vl+=e[c[ch]].y+x[s]-x[sl];
ll vr=query(srt[2],1,1,m2,1,to[c[ch]]);
if (vr!=linf) vr+=e[c[ch]].y+x[sr]-x[s];
modify2(slp,1,1,m2,to[c[ch]],to[c[ch]]);
modify2(srp,1,1,m2,to[c[ch]],to[c[ch]]);
if (vl!=linf) {
modify(slt[0],1,1,m2,to[c[ch]],vl-(x[s]-x[sl]));
modify(slt[1],1,1,m2,to[c[ch]],vl-(x[s]-x[sl])+rec[to[c[ch]]]);
modify(slt[2],1,1,m2,to[c[ch]],vl-(x[s]-x[sl])-rec[to[c[ch]]]);
}
if (vr!=linf) {
modify(srt[0],1,1,m2,to[c[ch]],vr-(x[sr]-x[s]));
modify(srt[1],1,1,m2,to[c[ch]],vr-(x[sr]-x[s])+rec[to[c[ch]]]);
modify(srt[2],1,1,m2,to[c[ch]],vr-(x[sr]-x[s])-rec[to[c[ch]]]);
}
if (vl!=linf&&vl+x[sr]-x[sl]<vr) {
modify(srt[0],1,1,m2,to[c[ch]],vl+x[sr]-x[sl]-(x[sr]-x[s]));
modify(srt[1],1,1,m2,to[c[ch]],vl+x[sr]-x[sl]-(x[sr]-x[s])+rec[to[c[ch]]]);
modify(srt[2],1,1,m2,to[c[ch]],vl+x[sr]-x[sl]-(x[sr]-x[s])-rec[to[c[ch]]]);
} else if (vr!=linf&&vr+x[sr]-x[sl]<vl) {
modify(slt[0],1,1,m2,to[c[ch]],vr+x[sr]-x[sl]-(x[s]-x[sl]));
modify(slt[1],1,1,m2,to[c[ch]],vr+x[sr]-x[sl]-(x[s]-x[sl])+rec[to[c[ch]]]);
modify(slt[2],1,1,m2,to[c[ch]],vr+x[sr]-x[sl]-(x[s]-x[sl])-rec[to[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,to[c[ch]]);
if (vl!=linf) vl+=e[c[ch]].y+x[s]-x[sl];
ll vr=query(srt[2],1,1,m2,1,to[c[ch]]);
if (vr!=linf) vr+=e[c[ch]].y+x[sr]-x[s];
modify2(slp,1,1,m2,to[c[ch]],to[c[ch]]);
modify2(srp,1,1,m2,to[c[ch]],to[c[ch]]);
if (vl!=linf) {
modify(slt[0],1,1,m2,to[c[ch]],vl-(x[s]-x[sl]));
modify(slt[1],1,1,m2,to[c[ch]],vl-(x[s]-x[sl])+rec[to[c[ch]]]);
modify(slt[2],1,1,m2,to[c[ch]],vl-(x[s]-x[sl])-rec[to[c[ch]]]);
}
if (vr!=linf) {
modify(srt[0],1,1,m2,to[c[ch]],vr-(x[sr]-x[s]));
modify(srt[1],1,1,m2,to[c[ch]],vr-(x[sr]-x[s])+rec[to[c[ch]]]);
modify(srt[2],1,1,m2,to[c[ch]],vr-(x[sr]-x[s])-rec[to[c[ch]]]);
}
if (vl!=linf&&vl+x[sr]-x[sl]<vr) {
modify(srt[0],1,1,m2,to[c[ch]],vl+x[sr]-x[sl]-(x[sr]-x[s]));
modify(srt[1],1,1,m2,to[c[ch]],vl+x[sr]-x[sl]-(x[sr]-x[s])+rec[to[c[ch]]]);
modify(srt[2],1,1,m2,to[c[ch]],vl+x[sr]-x[sl]-(x[sr]-x[s])-rec[to[c[ch]]]);
} else if (vr!=linf&&vr+x[sr]-x[sl]<vl) {
modify(slt[0],1,1,m2,to[c[ch]],vr+x[sr]-x[sl]-(x[s]-x[sl]));
modify(slt[1],1,1,m2,to[c[ch]],vr+x[sr]-x[sl]-(x[s]-x[sl])+rec[to[c[ch]]]);
modify(slt[2],1,1,m2,to[c[ch]],vr+x[sr]-x[sl]-(x[s]-x[sl])-rec[to[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) {
ll res=query(srt[0],1,1,m2,i,i);
if (res!=linf&&ans>res+x[sr]-x[s]+rec[i]) {
ans=res+x[sr]-x[s]+rec[i];
ansp=i;
}
}
//cout<<ans<<endl;
if (flag) ans=-1;
if (ans==linf) ans=-1;
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:393:6: warning: variable 'ansp' set but not used [-Wunused-but-set-variable]
393 | int ansp;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
9856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
13432 KB |
Output is correct |
| 2 |
Runtime error |
87 ms |
32376 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
13432 KB |
Output is correct |
| 2 |
Runtime error |
87 ms |
32376 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
9856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
