Submission #1071603

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071603		Gromp15	Sky Walking (IOI19_walk)	C++17	24 / 100	4054 ms	682888 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<multiset<ll>> tree;
	seg(int n) : N(1<<(__lg(n)+1)), tree(2*N) {}
	void add(int pos, ll x) {
		for (int i = pos + N; i; i >>= 1) {
			tree[i].insert(x);
		}
	}
	void del(int pos, ll x) {
		for (int i = pos + N; i; i >>= 1) {
			tree[i].erase(tree[i].find(x));
		}
	}
	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].size() ? *tree[node].begin() : INF;
		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]});
		if (lines.empty()) {
			return s == g ? 0 : -1;
		}
		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);
		int t = 0;
		for (int i = 0; i < m; i++) {
			while (t <= min(n-1, lines[i][0])) {
				for (int x : rem[t]) {
					st1.del(lines[x][2], dp[x] - y[lines[x][2]]);
					st2.del(lines[x][2], dp[x] + y[lines[x][2]]);
				}
				t++;
			}
			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));
			st1.add(lines[i][2], dp[i] - y[lines[i][2]]);
			st2.add(lines[i][2], dp[i] + y[lines[i][2]]);
			if (lines[i][1] + 1 < n) rem[lines[i][1]+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: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43