Submission #313197

#TimeUsernameProblemLanguageResultExecution timeMemory
313197AngelKnowsSky Walking (IOI19_walk)C++14
0 / 100
87 ms32376 KiB
#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 (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:393:6: warning: variable 'ansp' set but not used [-Wunused-but-set-variable]
  393 |  int ansp;
      |      ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...