oj.uz

Submission #1071577

# Submission time Handle Problem Language Result Execution time Memory
1071577 2024-08-23T09:01:35 Z Gromp15 Sky Walking (IOI19_walk) C++17
0 / 100
 1781 ms 217256 KB 
#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);
		int t = 0;
		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));
			st1.update(lines[i][2], dp[i] - y[lines[i][2]]);
			st2.update(lines[i][2], dp[i] + y[lines[i][2]]);
			while (t <= min(n-1, lines[i][0])) {
				for (int x : rem[t]) {
					st1.update(lines[x][2], INF);
					st2.update(lines[x][2], INF);
				}
				t++;
			}
			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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Incorrect 0 ms 348 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1335 ms 141972 KB Output is correct
4 Correct 811 ms 158704 KB Output is correct
5 Correct 363 ms 99836 KB Output is correct
6 Correct 318 ms 90356 KB Output is correct
7 Correct 350 ms 99832 KB Output is correct
8 Correct 1781 ms 180264 KB Output is correct
9 Correct 453 ms 102968 KB Output is correct
10 Correct 1149 ms 217256 KB Output is correct
11 Correct 383 ms 77056 KB Output is correct
12 Incorrect 108 ms 15816 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 3288 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 3288 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Incorrect 0 ms 348 KB Output isn't correct
17 Halted 0 ms 0 KB -