Submission #1058595

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058595		Unforgettablepl	Sky Walking (IOI19_walk)	C++17	57 / 100	1994 ms	1048728 KiB

walk

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

const long long INF = 1e15;

long long min_distance2(vector<int> x,vector<int> h,vector<int> l,
					   vector<int> r,vector<int> y,int s,int g){
	int n = x.size();
	int m = l.size();
	vector<vector<pair<int,int>>> points(n);
	vector<vector<pair<int,int>>> adj;
	int S = 0;
	vector<tuple<int,int,int>> skywalks;
	for(int i=0;i<m;i++)skywalks.emplace_back(y[i],l[i],r[i]);
	sort(skywalks.rbegin(), skywalks.rend());
	auto add_point = [&](int x,int h) {
		adj.emplace_back();
		if(!points[x].empty())adj[S].emplace_back(points[x].back().first,points[x].back().second-h);
		if(!points[x].empty())adj[points[x].back().first].emplace_back(S,points[x].back().second-h);
		points[x].emplace_back(S,h);
		return S++;
	};
	vector<pair<int,int>> sorted_buildings;
	for(int i=0;i<n;i++)sorted_buildings.emplace_back(h[i],i);
	sort(sorted_buildings.rbegin(),sorted_buildings.rend());
	auto iterb = sorted_buildings.begin();
	set<int> active;
	for(int i=0;i<m;i++){
		auto [height,left,right] = skywalks[i];
		while(iterb!=sorted_buildings.end() and iterb->first>=height)active.insert((iterb++)->second);
		auto last_point = add_point(left,height);
		auto last_x = x[left];
		for(auto iter=active.upper_bound(left);true;iter++){
			int j = *iter;
			auto curr_point = add_point(j,height);
			adj[curr_point].emplace_back(last_point,x[j]-last_x);
			adj[last_point].emplace_back(curr_point,x[j]-last_x);
			last_point=curr_point;
			last_x=x[j];
			if(*iter==right)break;
		}
	}
	for(int i=0;i<n;i++)add_point(i,0);
	priority_queue<pair<long long,int>> q;
	vector<bool> visited(S);
	s = points[s].back().first;
	g = points[g].back().first;
	q.emplace(0,s);
	while(!q.empty()) {
		auto [dist,idx] = q.top();q.pop();dist=-dist;
		if(visited[idx])continue;
		visited[idx]=true;
		if(idx==g)return dist;
		for(auto&[v,c]:adj[idx])if(!visited[v])q.emplace(-dist-c,v);
	}
	return -1;
}

long long min_distance(vector<int> x,vector<int> h,vector<int> l,
					   vector<int> r,vector<int> y,int s,int g){
	int n = x.size();
	if(s!=0 or g!=n-1)return min_distance2(x,h,l,r,y,s,g);
	int m = l.size();
	vector<vector<int>> starters(n);
	vector<vector<int>> ends(n);
	for(int i=0;i<m;i++) {
		starters[l[i]].emplace_back(y[i]);
		ends[r[i]].emplace_back(y[i]);
	}
	multiset<pair<int,long long>> offers;
	ends[0].emplace_back(0);
	offers.emplace(0,0);
	for(int i=0;i<n-1;i++) {
		for(int&ht:starters[i]) {
			auto iter = offers.lower_bound({ht,0});
			long long bestopt = INF;
			if(iter!=offers.end()) {
				// try
				bestopt=min(bestopt,iter->first-ht + iter->second);
			}
			if(iter!=offers.begin()) {
				--iter;
				// try
				bestopt=min(bestopt,ht-iter->first+iter->second);
			}
			offers.emplace(ht,bestopt);
		}
		for(int&ht:ends[i]) {
			offers.erase(offers.lower_bound({ht,0}));
		}
	}
	if(offers.empty())return -1;
	long long ans = x[g]-x[s]+offers.begin()->second+offers.begin()->first;
	if(ans>=INF)return -1;
	return ans;
}

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