Submission #542677

#	Time	Username	Problem	Language	Result	Execution time	Memory
542677		jamezzz	Sky Walking (IOI19_walk)	C++17	100 / 100	1382 ms	145680 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#define getchar_unlocked getchar
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll,int> li;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;
mt19937 rng(time(0));

#define mod 1000000007

struct skywalk{
	int l,r,h;
};

#define maxn 100005

int n,m;
vector<ii> nodes,nodes2;
vector<skywalk> skywalks;
vector<int> add[maxn],rem[maxn];
ll dist[3000005];
priority_queue<li,vector<li>,greater<li>> pq;
vii AL[3000005];

void proc(int a,vi &h){
	vector<skywalk> tmp;
	vector<ii> pv,nx;
	pv.pb({h[a],a});
	nx.pb({h[a],a});
	for(int i=a-1;i>=0;--i){
		if(h[i]>pv.back().fi){
			pv.pb({h[i],i});
		}
	}
	for(int i=a+1;i<n;++i){
		if(h[i]>nx.back().fi){
			nx.pb({h[i],i});
		}
	}
	for(skywalk &sw:skywalks){
		if(sw.l<a&&a<sw.r){
			int p1=lower_bound(all(pv),ii(sw.h,-1))-pv.begin();
			int p2=lower_bound(all(nx),ii(sw.h,-1))-nx.begin();
			if(sw.l!=pv[p1].se)tmp.pb({sw.l,pv[p1].se,sw.h});
			if(pv[p1].se!=nx[p2].se)tmp.pb({pv[p1].se,nx[p2].se,sw.h});
			if(nx[p2].se!=sw.r)tmp.pb({nx[p2].se,sw.r,sw.h});
		}
		else tmp.pb(sw);
	}
	swap(tmp,skywalks);
}

ll min_distance(vi x,vi h,vi l,vi r,vi y,int s,int g){
	n=sz(x);m=sz(l);
	for(int i=0;i<m;++i){
		skywalks.pb({l[i],r[i],y[i]});
	}
	proc(s,h);proc(g,h);
	
	for(skywalk &sw:skywalks){
		add[sw.l].pb(sw.h);
		rem[sw.r].pb(sw.h);
	}
	
	multiset<int> ms;
	ms.insert(0);
	for(int i=0;i<n;++i){
		for(int j:add[i])ms.insert(j);
		for(int j:add[i]){
			nodes.pb({x[i],j});
			nodes.pb({x[i],*(--ms.lower_bound(j))});
		}
		for(int j:rem[i]){
			nodes.pb({x[i],j});
			nodes.pb({x[i],*(--ms.lower_bound(j))});
		}
		for(int j:rem[i])ms.erase(ms.find(j));
	}
	disc(nodes);
	
	for(ii pr:nodes)nodes2.pb({pr.se,pr.fi});
	sort(all(nodes2));
	
	for(int i=1;i<sz(nodes);++i){
		if(nodes[i-1].fi==nodes[i].fi){
			AL[i-1].pb({i,nodes[i].se-nodes[i-1].se});
			AL[i].pb({i-1,nodes[i].se-nodes[i-1].se});
		}
	}
	
	for(skywalk &sw:skywalks){
		int s=lower_bound(all(nodes2),ii(sw.h,x[sw.l]))-nodes2.begin();
		while(nodes2[s]!=ii(sw.h,x[sw.r])){
			ii p1={nodes2[s].se,nodes2[s].fi};
			ii p2={nodes2[s+1].se,nodes2[s+1].fi};
			int u=lower_bound(all(nodes),p1)-nodes.begin();
			int v=lower_bound(all(nodes),p2)-nodes.begin();
			int w=p2.fi-p1.fi;
			AL[u].pb({v,w});
			AL[v].pb({u,w});
			++s;
		}
	}
	
	for(int i=0;i<sz(nodes);++i)dist[i]=LINF;
	int src=lower_bound(all(nodes),ii(x[s],0))-nodes.begin();
	if(src==sz(nodes)||nodes[src]!=ii(x[s],0))return -1;
	dist[src]=0;pq.push({0,src});
	
	while(!pq.empty()){
		auto[d,u]=pq.top();
		pq.pop();
		for(auto[v,w]:AL[u]){
			if(dist[v]>dist[u]+w){
				dist[v]=dist[u]+w;
				pq.push({dist[v],v});
			}
		}
	}
	
	int f=lower_bound(all(nodes),ii(x[g],0))-nodes.begin();
	if(f==sz(nodes)||nodes[f]!=ii(x[g],0))return -1;
	ll ans=dist[f];
	if(ans==LINF)ans=-1;
	return ans;
}

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