Submission #610890

#	Time	Username	Problem	Language	Result	Execution time	Memory
610890		fvogel499	Sky Walking (IOI19_walk)	C++17	33 / 100	300 ms	39072 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, int>
#define f first
#define s second

#define int long long
#define size(x) (int)((x).size())

const int inf = 1e18;

int min_distance(std::vector<signed> pos, std::vector<signed> heightOf, std::vector<signed> leftP, std::vector<signed> rightP, std::vector<signed> yLevel, signed s, signed g) {
	const int n = size(pos);
	const int nbP = size(leftP);
	vector<int> finishAt [n];
	for (int i = 0; i < nbP; i++) {
		finishAt[rightP[i]].push_back(yLevel[i]);
	}
	finishAt[0].push_back(0);
	map<int, int> dp [n];
	for (int i : finishAt[n-1]) {
		dp[n-1][i] = i;
	}
	vector<pair<int, int>> addAt [n];
	vector<pair<int, int>> removeAt [n];
	for (int i = 0; i < nbP; i++) {
		addAt[rightP[i]].push_back({yLevel[i], rightP[i]});
		removeAt[leftP[i]].push_back({yLevel[i], rightP[i]});
	}
	map<int, int> m;
	for (int i = n-1; i >= 0; i--) {
		if (i < n-1) {
			for (int j : finishAt[i]) {
				dp[i][j] = inf;
				auto it = m.upper_bound(j);
				if (!m.empty() && it != m.end()) {
					int loc = dp[it->second][it->first]+it->first-j;
					dp[i][j] = min(dp[i][j], loc);
				}
				if (!m.empty() && it != m.begin()) {
					it = prev(it);
					int loc = dp[it->second][it->first]+j-it->first;
					dp[i][j] = min(dp[i][j], loc);
				}
			}
		}
		for (auto j : removeAt[i]) {
			assert(m.count(j.f));
			m.erase(j.f);
		}
		for (auto j : addAt[i]) {
			assert(!m.count(j.f));
			m[j.f] = j.s;
		}
	}
	int res = dp[0][0];
	res += (int)(pos[n-1]-pos[0]);
	if (res >= inf) res = -1;
	return res;
}

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