Submission #293884

#	Time	Username	Problem	Language	Result	Execution time	Memory
293884		PeppaPig	Sky Walking (IOI19_walk)	C++14	24 / 100	2008 ms	302256 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_e[N], pos_b[N];
long dp[N];
vector<pii> coord, g[N];
vector<int> inter[N];

int get(pii x) {
	return lower_bound(coord.begin(), coord.end(), x) - coord.begin();
}

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_e, pos_e + N, 0), iota(pos_b, pos_b + N, 0);
	sort(pos_e, pos_e + m, [&](int a, int b) {
		return y[a] > y[b];	
	});
	sort(pos_b, pos_b + n, [&](int a, int b) {
		return h[a] > h[b];
	});

	coord.emplace_back(x[su], 0), coord.emplace_back(x[eu], 0);
	set<int> S;
	int ptr = 0;
	for(int i = 0; i < m; i++) {
		while(ptr < n && h[pos_b[ptr]] >= y[pos_e[i]]) 
			S.emplace(pos_b[ptr++]);

		auto L = S.lower_bound(l[pos_e[i]]), R = S.upper_bound(r[pos_e[i]]);
		for( ; L != R; L++)
			coord.emplace_back(x[*L], y[pos_e[i]]);
	}

	sort(coord.begin(), coord.end());
	coord.resize(unique(coord.begin(), coord.end()) - coord.begin());

	//for(pii p : coord) printf("(%lld %lld)\n", p.x, p.y);

	inter[su].emplace_back(0), inter[eu].emplace_back(0);
	S.clear(), ptr = 0;
	for(int i = 0; i < m; i++) {
		while(ptr < n && h[pos_b[ptr]] >= y[pos_e[i]])
			S.emplace(pos_b[ptr++]);

		auto L = S.lower_bound(l[pos_e[i]]), R = S.upper_bound(r[pos_e[i]]);
		for(int p = -1, d = -1; L != R; L++) {
			int u = get(pii(x[*L], y[pos_e[i]]));
			if(p != -1) {
				g[u].emplace_back(p, x[*L] - d), g[p].emplace_back(u, x[*L] - d);
				//printf("edge (%lld %lld) (%lld %lld) = %d\n", coord[u].x, coord[u].y, coord[p].x, coord[p].y, x[j] - d);
			}
			p = u, d = x[*L];
			inter[*L].emplace_back(y[pos_e[i]]);	
		}
	}
	for(int i = 0; i < n; i++) {
		sort(inter[i].begin(), inter[i].end());
		inter[i].resize(unique(inter[i].begin(), inter[i].end()) - inter[i].begin());

		for(int j = 0; j < (int)inter[i].size() - 1; j++) {
			int d = inter[i][j + 1] - inter[i][j];
			int u = get(pii(x[i], inter[i][j])), v = get(pii(x[i], inter[i][j + 1]));
			g[u].emplace_back(v, d), g[v].emplace_back(u, d);

			//printf("edge (%lld %lld) (%lld %lld) = %d\n", coord[u].x, coord[u].y, coord[v].x, coord[v].y, d);
		}
	}

	fill_n(dp, N, 1e18);
	priority_queue<pii, vector<pii>, greater<pii> > Q;

	Q.emplace(dp[get(pii(x[su], 0))] = 0, get(pii(x[su], 0)));
	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 ret = dp[get(pii(x[eu], 0))];
	return ret == 1e18 ? -1 : ret;
}

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