Submission #312692

#	Time	Username	Problem	Language	Result	Execution time	Memory
312692		AngelKnows	Sky Walking (IOI19_walk)	C++14	0 / 100	46 ms	9208 KiB

walk

#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 (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:291:6: warning: variable 'ansp' set but not used [-Wunused-but-set-variable]
  291 |  int ansp;
      |      ^~~~

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