Submission #737928

#	Time	Username	Problem	Language	Result	Execution time	Memory
737928		bobthebuilder	Sky Walking (IOI19_walk)	C++17	33 / 100	619 ms	165640 KiB

walk

#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define pb push_back
#define lowb(x) (x&(-x))
#define ALL(_x) _x.begin(),_x.end()
#define pii pair<ll,int>
#define f first
#define s second
#define SORT_UNIQUE(x) sort(ALL(x)),x.erase(unique(ALL(x)),x.end())
#define ll long long
const ll INF64=4e18;
const int maxn=2e6+5;
vector<pii> gr[maxn];
void add(int a,int b,int w){
	gr[a].pb({b,w}),gr[b].pb({a,w});
}
vector<pii> pts[maxn];
ll dist[maxn];
long long min_distance(std::vector<int> xx, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
	int n=sz(xx),m=sz(l);
	vector<pii> v;
	REP(i,n){
		v.pb({h[i],i});
	}
	sort(ALL(v)),reverse(ALL(v));;
	for(int zz:{s,g}){
		m=sz(l);
		vector<pii> vv;
		REP(i,m){
			vv.pb({y[i],i});
		}
		set<int> ss;
		sort(ALL(vv));
		reverse(ALL(vv));
		int p=0;
		for(auto x:vv){
			if(r[x.s]<=zz or l[x.s]>=zz) continue;
			while(p<n and v[p].f>=x.f){
				ss.insert(v[p].s);
				++p;
			}
			int a=(*prev(ss.upper_bound(zz))),b=(*ss.lower_bound(zz));
			l.pb(l[x.s]),r.pb(a),y.pb(x.f);
			l.pb(a),r.pb(b),y.pb(x.f);
			l.pb(b),r.pb(r[x.s]),y.pb(x.f);
		}
	}
	vector<pii> vv;
	REP(i,m){
		vv.pb({y[i],i});
	}
	sort(ALL(vv));
	reverse(ALL(vv));
	int cur=0;
	set<int> ss;
	int p=0;
	for(auto x:vv){
		while(p<n and v[p].f>=x.f){
			ss.insert(v[p].s);
			++p;
		}
		int a=l[x.s],b=r[x.s];
		ss.insert(a),ss.insert(b);
		auto it=ss.lower_bound(a);
		int pp=-1;
		vector<int> del;
		while(it!=ss.end() and (*it)<=b){
			int z=(*it);
			if(sz(pts[z])){
			auto pv=pts[z].back();
			add(pv.s,cur,pv.f-x.f);
			}
			pts[z].pb({x.f,cur});
			if(pp!=-1) add(cur-1,cur,xx[z]-xx[pp]);
			pp=z;
			++cur;
			if(z!=a and z!=b){
				del.pb(z);
			}
			++it;
		}
		for(int x:del) ss.erase(x);
	}
	for(int z:{s,g}){
		if(!sz(pts[z])){
			return -1;
		}
		auto pv=pts[z].back();
		add(pv.s,cur++,pv.f);
	}
	REP(i,cur) dist[i]=INF64;
	priority_queue<pii,vector<pii>,greater<pii>> pq;
	pq.push({0,cur-2});
	dist[cur-2]=0;
	while(sz(pq)){
		int z=pq.top().s;
		if(pq.top().f>dist[z]){
			pq.pop();
			continue;
		}
		pq.pop();
		for(auto x:gr[z]){
			if(dist[x.f]>dist[z]+x.s){
				dist[x.f]=dist[z]+x.s;
				pq.push({dist[x.f],x.f});
			}
		}
	}
	if(dist[cur-1]==INF64) dist[cur-1]=-1;
	return dist[cur-1];
}

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