Submission #313186

#	Time	Username	Problem	Language	Result	Execution time	Memory
313186		AngelKnows	Sky Walking (IOI19_walk)	C++14	0 / 100	86 ms	32248 KiB

walk

#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][8*N],srt[3][8*N];
int lstop,rstop,dir;
ll maxh;
int slp[8*N],srp[8*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));
}
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);
}
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) {
						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));
					ll v2=query(srt[1],1,1,m2,to[it],find2(srp,h[sr]));
					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) {
						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));
					ll v2=query(slt[1],1,1,m2,to[it],find2(slp,h[sl]));
					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!=n) 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;
      |      ^~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43