Submission #596717

#	Time	Username	Problem	Language	Result	Execution time	Memory
596717		Temmie	Sky Walking (IOI19_walk)	C++17	33 / 100	184 ms	20044 KiB

walk

#include <bits/stdc++.h>

long long min_distance(std::vector <int> a, std::vector <int> h,
std::vector <int> l, std::vector <int> r, std::vector <int> y,
int s, int e) {
	if (e < s) {
		std::swap(s, e);
	}
	int n = a.size();
	int m = y.size();
	std::vector <std::vector <std::pair <int, bool>>> inds(n + 1);
	for (int i = 0; i < m; i++) {
		inds[l[i]].emplace_back(y[i], true);
		inds[r[i] + 1].emplace_back(y[i], false);
	}
	inds[1].emplace_back(0, false);
	std::map <int, long long> mp;
	mp[0] = 0;
	std::set <int> st;
	for (int i = 0; i < n; i++) {
		for (auto p : inds[i]) {
			if (!p.second && !st.count(p.first)) {
				mp.erase(p.first);
			}
		}
		st.clear();
		for (auto p : inds[i]) {
			if (p.second) {
				auto it = mp.lower_bound(p.first);
				long long val = 1LL << 60;
				if (it != mp.end()) {
					val = std::min(val, it->second - p.first + it->first);
				}
				if (it != mp.begin()) {
					it--;
					val = std::min(val, it->second - it->first + p.first);
				}
				if (val != (1LL << 60)) {
					mp[p.first] = val;
					st.insert(p.first);
				}
			}
		}
	}
	if (mp.empty()) {
		return -1;
	}
	return mp.begin()->first + mp.begin()->second + a[n - 1] - a[0];
}

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