Submission #422793

#	Time	Username	Problem	Language	Result	Execution time	Memory
422793		KoD	Sky Walking (IOI19_walk)	C++17	24 / 100	4102 ms	1048580 KiB

walk

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

using ll = long long;
template <class T> using Vec = std::vector<T>;
template <class T> using Heap = std::priority_queue<T, Vec<T>, std::greater<T>>;

constexpr ll INF = std::numeric_limits<ll>::max() / 2;

struct RMQ {
	int size;
	Vec<ll> min;
	RMQ(const int n): size(n), min(2 * n, INF) {}
	void assign(int i, const ll x) {
		i += size;
		min[i] = x;
		while (i > 1) {
			i >>= 1;
			min[i] = std::min(min[2 * i], min[2 * i + 1]);
		}
	}
	ll fold(int l, int r) const {
		l += size;
		r += size;
		ll x = INF;
		while (l < r) {
			if (l & 1) x = std::min(x, min[l++]);
			if (r & 1) x = std::min(x, min[--r]);
			l >>= 1;
			r >>= 1;
		}
		return x;
	}
};

ll min_distance(Vec<int> x, Vec<int> h, Vec<int> l, Vec<int> r, Vec<int> y, int s, int g) {
	const int n = (int) x.size();
	const int m = (int) y.size();
	// if (s == 0 and g == n - 1) {
	// 	Vec<Vec<int>> start(n), end(n);
	// 	for (int i = 0; i < m; ++i) {
	// 		start[l[i]].push_back(i);
	// 		end[r[i]].push_back(i);
	// 	}
	// 	Vec<int> cmp = y;
	// 	std::sort(cmp.begin(), cmp.end());
	// 	cmp.erase(std::unique(cmp.begin(), cmp.end()), cmp.end());
	// 	Vec<int> idx(m);
	// 	for (int i = 0; i < m; ++i) {
	// 		idx[i] = std::lower_bound(cmp.begin(), cmp.end(), y[i]) - cmp.begin();
	// 	}
	// 	const int sz = (int) cmp.size();
	// 	RMQ down(sz), up(sz);
	// 	Vec<int> alive(sz);
	// 	for (const int j: start[0]) {
	// 		down.assign(idx[j], y[j] - y[j]);
	// 		up.assign(idx[j], y[j] + y[j]);
	// 		alive[idx[j]] += 1;			
	// 	}
	// 	for (int i = 1; i < n; ++i) {
	// 		const int height = std::upper_bound(cmp.begin(), cmp.end(), h[i]) - cmp.begin();
	// 		for (const auto j: start[i]) {
	// 			const ll a = down.fold(0, idx[j] + 1);
	// 			const ll b = up.fold(idx[j], height);
	// 			ll d = INF;
	// 			if (a != INF) {
	// 				d = std::min(d, a + y[j]);
	// 			}
	// 			if (b != INF) {
	// 				d = std::min(d, b - y[j]);
	// 			}
	// 			if (d != INF) {
	// 				down.assign(idx[j], d - y[j]);
	// 				up.assign(idx[j], d + y[j]);
	// 			} else {
	// 				down.assign(idx[j], INF);
	// 				down.assign(idx[j], INF);
	// 			}
	// 			alive[idx[j]] += 1;
	// 		}
	// 		if (i != n - 1) {
	// 			for (const auto j: end[i]) {
	// 				alive[idx[j]] -= 1;
	// 				if (alive[idx[j]] == 0) {
	// 					down.assign(idx[j], INF);
	// 					up.assign(idx[j], INF);
	// 				}
	// 			}
	// 		}
	// 	}
	// 	ll ret = up.fold(0, sz);
	// 	return ret == INF ? -1 : (ret + x[n - 1] - x[0]);
	// }
	Vec<std::tuple<int, int, int>> query;
	query.reserve(n + m);
	for (int i = 0; i < n; ++i) {
		query.emplace_back(h[i], n, i);
	}
	for (int i = 0; i < m; ++i) {
		query.emplace_back(y[i], l[i], r[i]);
	}
	Vec<Vec<ll>> height(n);
	Vec<Vec<Vec<std::pair<int, int>>>> graph(n);
	std::sort(query.rbegin(), query.rend());
	std::map<int, int> alive;
	for (const auto [t, u, v]: query) {
		if (u == n) {
			alive.emplace(x[v], v);
		} else {
			const auto end = alive.upper_bound(x[v]);
			int li = -1, lj = -1;
			for (auto itr = alive.lower_bound(x[u]); itr != end; ++itr) {
				const auto i = itr -> second;
				if (height[i].empty() or height[i].back() != t) {
					height[i].push_back(t);
					graph[i].emplace_back();
				}
				const auto j = (int) height[i].size() - 1;
				if (li != -1) {
					graph[i][j].emplace_back(li, lj);
					graph[li][lj].emplace_back(i, j);
				}
				li = i, lj = j;
			}
		}
	}
	Vec<Vec<ll>> dist(n);
	for (int i = 0; i < n; ++i) {
		height[i].push_back(0);
		graph[i].emplace_back();
		dist[i].assign(height[i].size(), INF);
	}
	Heap<std::tuple<ll, int, int>> heap;
	const auto push = [&](const int i, const int j, const ll d) {
		if (dist[i][j] > d) {
			dist[i][j] = d;
			heap.emplace(d, i, j);
		}
	};
	push(s, (int) height[s].size() - 1, 0);
	while (!heap.empty()) {
		const auto [d, i, j] = heap.top();
		heap.pop();
		if (dist[i][j] < d) {
			continue;
		}
		for (const auto [ni, nj]: graph[i][j]) {
			push(ni, nj, d + std::abs(x[i] - x[ni]));
		}
		if (j > 0) {
			push(i, j - 1, d + std::abs(height[i][j] - height[i][j - 1]));
		}
		if (j + 1 < (int) height[i].size()) {
			push(i, j + 1, d + std::abs(height[i][j + 1] - height[i][j]));
		}
	}
	const auto ret = dist[g][height[g].size() - 1];
	return ret == INF ? -1 : ret;
}

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