Submission #294116

#	Time	Username	Problem	Language	Result	Execution time	Memory
294116		PeppaPig	Sky Walking (IOI19_walk)	C++14	33 / 100	390 ms	67948 KiB

walk

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

#define long long long
#define pii pair<long, long>
#define x first
#define y second

using namespace std;

const int N = 1.2e6 + 5;

int n, m;
int pos[N];
long dp[N];
vector<pii> g[N];

long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int su, int eu) {
	n = (int)x.size(), m = (int)l.size();
	iota(pos, pos + N, 0);

	sort(pos, pos + m, [&](int a, int b) {
		return l[a] < l[b];
	});	

	priority_queue<pii, vector<pii>, greater<pii> > rem, Q;
	set<pii> active;
	for(int _ = 0; _ < m; _++) {
		int i = pos[_];
		while(!rem.empty() && rem.top().x < l[i]) {
			active.erase(pii(y[rem.top().y], rem.top().y));
			rem.pop();
		}
		auto it = active.lower_bound(pii(y[i], -1e9));
		if(it != active.end()) {
			g[i].emplace_back(it->y, it->x - y[i]);
			g[it->y].emplace_back(i, it->x - y[i]);
		}
		if(it != active.begin()) {
			--it;
			g[i].emplace_back(it->y, y[i] - it->x);
			g[it->y].emplace_back(i, y[i] - it->x);
		}
		active.emplace(y[i], i), rem.emplace(r[i], i);
	}

	fill_n(dp, N, 1e18);
	for(int i = 0; i < m; i++) if(l[i] == 0)
		Q.emplace(dp[i] = y[i], i);	

	while(!Q.empty()) {
		pii u = Q.top(); Q.pop();
		if(dp[u.y] != u.x) continue;
		for(pii v : g[u.y]) if(u.x + v.y < dp[v.x])
			Q.emplace(dp[v.x] = u.x + v.y, v.x);
	}

	long ans = 1e18;
	for(int i = 0; i < m; i++) if(r[i] == n - 1)
		ans = min(ans, dp[i] + y[i]);
	
	return ans == 1e18 ? -1 : ans + x[eu] - x[su];
}

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