Submission #596713

#	Time	Username	Problem	Language	Result	Execution time	Memory
596713		Temmie	Sky Walking (IOI19_walk)	C++17	0 / 100	42 ms	6324 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::map <int, std::vector <int>> ind_seg_start_here;
	std::map <int, std::vector <int>> ind_seg_end_here;
	for (int i = 0; i < m; i++) {
		ind_seg_start_here[a[l[i]]].push_back(i);
		ind_seg_end_here[a[r[i]]].push_back(i);
	}
	std::map <int, std::map <int, long long>> arrive;
	std::map <int, int> active;
	arrive[0][0] = 0;
	std::set <int> idx;
	for (int x : a) {
		idx.insert(x);
	}
	for (int i : idx) {
		for (int x : ind_seg_end_here[i]) {
			active.erase(y[x]);
		}
		for (int x : ind_seg_start_here[i]) {
			active[y[x]] = x;
		}
		for (auto p : arrive[i]) {
			auto it = active.lower_bound(p.first);
			if (it != active.end()) {
				auto itt = arrive[a[r[it->second]]].find(y[it->second]);
				if (itt == arrive[a[r[it->second]]].end() ||
				itt->second > p.second + abs(p.first - y[it->second])) {
					arrive[a[r[it->second]]][y[it->second]] =
					p.second + abs(p.first - y[it->second]) + (a[r[it->second]] - i);
				}
			}
			it = active.upper_bound(p.first);
			if (it != active.begin()) {
				it--;
				auto itt = arrive[a[r[it->second]]].find(y[it->second]);
				if (itt == arrive[a[r[it->second]]].end() ||
				itt->second > p.second + abs(p.first - y[it->second])) {
					arrive[a[r[it->second]]][y[it->second]] =
					p.second + abs(p.first - y[it->second]) + (a[r[it->second]] - i);
				}
			}
		}
	}
	long long ans = 1LL << 60;
	for (auto p : arrive[a[n - 1]]) {
		ans = std::min(ans, p.second + p.first);
	}
	return ans;
}

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