Submission #723928

#	Time	Username	Problem	Language	Result	Execution time	Memory
723928		GrandTiger1729	Sky Walking (IOI19_walk)	C++17	33 / 100	184 ms	21544 KiB

walk

#include "walk.h"
#ifndef EVAL
#include "grader.cpp"
#endif

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

const long long INF = 1e18;
long long min_distance(vector<int> a, vector<int> h, vector<int> l, vector<int> r, vector<int> b, int s, int g){
	int n = a.size(), m = l.size();
	vector<vector<int>> ll(n), rr(n);
	for (int i = 0; i < m; i++){
		ll[l[i]].push_back(b[i]);
		rr[r[i]].push_back(b[i]);
	}
	map<int, long long> mp;
	for (int &j: ll[0])
		mp[j] = j;
	// cerr << "OK" << endl;
	for (int i = 1; i < n - 1; i++){
		set<int> vis;
		for (int &j: ll[i]){
			auto it = mp.lower_bound(j);
			if (it != mp.end()){
				if (it->first != j)
					mp[j] = it->second + it->first - j;
				else
					vis.insert(j);
			}
			if (mp.size() && it != mp.begin() && it->first != j){
				it--;
				if (mp.find(j) == mp.end())
					mp[j] = it->second + j - it->first;
				else
					mp[j] = min(mp[j], it->second + j - it->first);
			}
		}
		// cerr << "OK" << endl;
		for (int &j: rr[i]){
			if (vis.count(j))
				continue;
			auto it = mp.lower_bound(j);
			if (it == mp.end())
				continue;
			{
				auto it2 = it;
				it2++;
				if (it2 != mp.end())
					it2->second = min(it2->second, it->second + it2->first - j);
			}
			// cerr << "OKK" << endl;
			if (it != mp.begin()){
				auto it2 = it;
				it2--;
				it2->second = min(it2->second, it->second + j - it2->first);
			}
			mp.erase(it);
		}
		// cerr << i << ' ' << mp.size() << endl;
		// for (auto &it: mp)
		// 	cerr << it.first << ' ' << it.second << endl;
		// cerr << endl;
	}
	long long ans = INF;
	for (auto &it: mp){
		ans = min(ans, it.first + it.second);
	}
	ans += a[g] - a[s];
	return ans >= INF? -1: ans;
}

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