Submission #1071569

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071569		Gromp15	Sky Walking (IOI19_walk)	C++17	0 / 100	1800 ms	216388 KiB

walk

#include <bits/stdc++.h>
#define ll long long
#define ar array
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#include "walk.h"
using namespace std;
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

const ll INF = 1e18;

struct seg {
	int N; vector<ll> tree;
	seg(int n) : N(1<<(__lg(n)+1)), tree(2*N, INF) {}
	void update(int pos, ll x) {
		tree[pos+N] = x;
		for (int i = (pos + N) >> 1; i; i >>= 1) tree[i] = min(tree[i*2], tree[i*2+1]);
	}
	ll query(int node, int nl, int nr, int ql, int qr) {
		if (ql > nr || qr < nl) return INF;
		if (ql <= nl && nr <= qr) return tree[node];
		int mid = (nl+nr)/2;
		return min(query(node*2, nl, mid, ql, qr), query(node*2+1, mid+1, nr, ql, qr));
	}
	ll query(int l, int r) {
		return query(1, 0, N-1, l, r);
	}
};

long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
	int n = sz(x), m = sz(l);
	if (s == 0 && g == n-1) {
		vector<ar<int, 3>> lines;
		for (int i = 0; i < m; i++) lines.push_back({l[i], r[i], y[i]});
		sort(all(lines));
		vector<ll> dp(m, INF);
		sort(all(y));
		y.erase(unique(all(y)), y.end());
		const int N = sz(y);
		auto compress = [&](int x) {
			return lower_bound(all(y), x) - y.begin();
		};
		seg st1(N), st2(N);
		for (auto &[l, r, y] : lines) y = compress(y);
		for (int i = 0; i < m; i++) if (lines[i][0] == 0) dp[i] = y[lines[i][2]];
		vector<vector<int>> rem(n);
		for (int i = 0; i < m; i++) {
			ckmin(dp[i], y[lines[i][2]] + st1.query(0, lines[i][2]));
			ckmin(dp[i], -y[lines[i][2]] + st2.query(lines[i][2], N-1));
			for (int x : rem[i]) { 
				st1.update(lines[x][2], INF);
				st2.update(lines[x][2], INF);
			}
			st1.update(lines[i][2], dp[i] - y[lines[i][2]]);
			st2.update(lines[i][2], dp[i] + y[lines[i][2]]);
			rem[lines[i][1]].emplace_back(i);
		}
		ll ans = INF;
		for (int i = 0; i < m; i++) if (lines[i][1] == n-1) ckmin(ans, dp[i] + y[lines[i][2]]);
		return ans == INF ? -1 : ans + x[n-1];
	}
	vector<int> idx(n);
	iota(all(idx), 0);
	sort(all(idx), [&](int x, int y) { return h[x] > h[y]; });
	vector<int> idx2(m);
	iota(all(idx2), 0);
	sort(all(idx2), [&](int X, int Y) { return y[X] > y[Y]; });
	set<int> who;
	vector<ar<int, 3>> edges;
	for (int i = 0, on = 0; i < m; i++) {
		int L = l[idx2[i]], R = r[idx2[i]], H = y[idx2[i]];
		while (on < n && h[idx[on]] >= H) {
			who.insert(idx[on++]);
		}
		int lst = -1;
		auto it1 = who.lower_bound(L);
		if (it1 == who.end() || *it1 > R) continue;
		lst = *it1;
		while (1) {
			auto it = who.upper_bound(lst);
			if (it == who.end() || *it > R) break;
			edges.push_back({lst, *it, H});
			lst = *it;
		}
	}
	vector<vector<int>> nodes(n);
	vector<map<int, vector<int>>> adj(n);
	for (auto [l, r, H] : edges) {
		nodes[l].emplace_back(H);
		nodes[r].emplace_back(H);
		adj[l][H].push_back(r);
		adj[r][H].push_back(l);
	}
	nodes[s].emplace_back(0);
	nodes[g].emplace_back(0);
	for (int i = 0; i < n; i++) {
		sort(all(nodes[i]));
		nodes[i].erase(unique(all(nodes[i])), nodes[i].end());
	}
	vector<map<int, ll>> dist(n);
	dist[s][0] = 0;
	priority_queue<ar<ll, 3>, vector<ar<ll, 3>>, greater<ar<ll, 3>>> q;
	q.push({0, s, 0});
	auto rlx = [&](int v1, int x1, int v2, int x2) {
		ll new_dist = dist[v1][x1] + abs(x[v1] - x[v2]) + abs(x1 - x2);
		if (!dist[v2].count(x2) || dist[v2][x2] > new_dist) {
			dist[v2][x2] = new_dist;
			q.push({dist[v2][x2], v2, x2});
		}
	};
	while (q.size()) {
		auto [cost, v, i] = q.top(); q.pop();
		if (cost != dist[v][i]) continue;
		auto it = upper_bound(all(nodes[v]), i);
		if (it != nodes[v].end() && *it <= h[v]) {
			rlx(v, i, v, *it);
		}
		assert(it != nodes[v].begin());
		it--;
		if (it != nodes[v].begin() && i <= h[v]) {
			rlx(v, i, v, *prev(it));
		}
		for (int x : adj[v][i]) {
			rlx(v, i, x, i);
		}
	}
	return dist[g].count(0) ? dist[g][0] : -1;
}

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