Submission #1058590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058590		Unforgettablepl	Sky Walking (IOI19_walk)	C++17	33 / 100	89 ms	21592 KiB

walk

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

const long long INF = 1e15;

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();
	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: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 15 / 15
• Subtask 4: 18 / 18
• Subtask 5: 0 / 43