oj.uz

답안 #1071606

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1071606 2024-08-23T09:17:16 Z Gromp15 Sky Walking (IOI19_walk) C++17
57 / 100
 4000 ms 927016 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<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] - x[0];
	}
	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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 408 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 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 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1258 ms 140528 KB Output is correct
4 Correct 815 ms 157520 KB Output is correct
5 Correct 384 ms 100088 KB Output is correct
6 Correct 371 ms 89584 KB Output is correct
7 Correct 382 ms 100004 KB Output is correct
8 Correct 1831 ms 178476 KB Output is correct
9 Correct 487 ms 102820 KB Output is correct
10 Correct 1203 ms 216348 KB Output is correct
11 Correct 407 ms 77052 KB Output is correct
12 Correct 208 ms 36260 KB Output is correct
13 Correct 256 ms 36192 KB Output is correct
14 Correct 142 ms 46084 KB Output is correct
15 Correct 192 ms 60220 KB Output is correct
16 Correct 180 ms 60568 KB Output is correct
17 Correct 199 ms 58612 KB Output is correct
18 Correct 614 ms 202404 KB Output is correct
19 Correct 6 ms 3164 KB Output is correct
20 Correct 83 ms 28976 KB Output is correct
21 Correct 69 ms 9924 KB Output is correct
22 Correct 59 ms 11736 KB Output is correct
23 Correct 479 ms 102204 KB Output is correct
24 Correct 151 ms 18668 KB Output is correct
25 Correct 75 ms 10444 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 3288 KB Output is correct
2 Correct 1130 ms 39232 KB Output is correct
3 Correct 1205 ms 39668 KB Output is correct
4 Correct 1204 ms 43820 KB Output is correct
5 Correct 1658 ms 203408 KB Output is correct
6 Correct 1870 ms 110552 KB Output is correct
7 Correct 246 ms 20428 KB Output is correct
8 Correct 218 ms 36296 KB Output is correct
9 Correct 1618 ms 119356 KB Output is correct
10 Correct 376 ms 101008 KB Output is correct
11 Correct 9 ms 2396 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 3288 KB Output is correct
2 Correct 1130 ms 39232 KB Output is correct
3 Correct 1205 ms 39668 KB Output is correct
4 Correct 1204 ms 43820 KB Output is correct
5 Correct 1658 ms 203408 KB Output is correct
6 Correct 1870 ms 110552 KB Output is correct
7 Correct 246 ms 20428 KB Output is correct
8 Correct 218 ms 36296 KB Output is correct
9 Correct 1618 ms 119356 KB Output is correct
10 Correct 376 ms 101008 KB Output is correct
11 Correct 9 ms 2396 KB Output is correct
12 Correct 1071 ms 39464 KB Output is correct
13 Correct 942 ms 43816 KB Output is correct
14 Correct 1599 ms 203416 KB Output is correct
15 Correct 755 ms 48836 KB Output is correct
16 Correct 763 ms 49092 KB Output is correct
17 Correct 708 ms 48408 KB Output is correct
18 Correct 732 ms 48584 KB Output is correct
19 Correct 784 ms 48788 KB Output is correct
20 Correct 403 ms 23948 KB Output is correct
21 Correct 18 ms 5212 KB Output is correct
22 Correct 447 ms 35272 KB Output is correct
23 Correct 363 ms 36296 KB Output is correct
24 Correct 425 ms 67016 KB Output is correct
25 Correct 258 ms 33996 KB Output is correct
26 Correct 536 ms 118620 KB Output is correct
27 Correct 1538 ms 176428 KB Output is correct
28 Correct 501 ms 36040 KB Output is correct
29 Correct 1965 ms 110876 KB Output is correct
30 Correct 227 ms 20684 KB Output is correct
31 Correct 1580 ms 119588 KB Output is correct
32 Correct 268 ms 52820 KB Output is correct
33 Correct 288 ms 52424 KB Output is correct
34 Correct 408 ms 62668 KB Output is correct
35 Correct 321 ms 24336 KB Output is correct
36 Correct 175 ms 16840 KB Output is correct
37 Correct 67 ms 9936 KB Output is correct
38 Correct 63 ms 11732 KB Output is correct
39 Correct 492 ms 102216 KB Output is correct
40 Correct 147 ms 18636 KB Output is correct
41 Correct 74 ms 10440 KB Output is correct

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 408 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 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 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1258 ms 140528 KB Output is correct
21 Correct 815 ms 157520 KB Output is correct
22 Correct 384 ms 100088 KB Output is correct
23 Correct 371 ms 89584 KB Output is correct
24 Correct 382 ms 100004 KB Output is correct
25 Correct 1831 ms 178476 KB Output is correct
26 Correct 487 ms 102820 KB Output is correct
27 Correct 1203 ms 216348 KB Output is correct
28 Correct 407 ms 77052 KB Output is correct
29 Correct 208 ms 36260 KB Output is correct
30 Correct 256 ms 36192 KB Output is correct
31 Correct 142 ms 46084 KB Output is correct
32 Correct 192 ms 60220 KB Output is correct
33 Correct 180 ms 60568 KB Output is correct
34 Correct 199 ms 58612 KB Output is correct
35 Correct 614 ms 202404 KB Output is correct
36 Correct 6 ms 3164 KB Output is correct
37 Correct 83 ms 28976 KB Output is correct
38 Correct 69 ms 9924 KB Output is correct
39 Correct 59 ms 11736 KB Output is correct
40 Correct 479 ms 102204 KB Output is correct
41 Correct 151 ms 18668 KB Output is correct
42 Correct 75 ms 10444 KB Output is correct
43 Correct 31 ms 3288 KB Output is correct
44 Correct 1130 ms 39232 KB Output is correct
45 Correct 1205 ms 39668 KB Output is correct
46 Correct 1204 ms 43820 KB Output is correct
47 Correct 1658 ms 203408 KB Output is correct
48 Correct 1870 ms 110552 KB Output is correct
49 Correct 246 ms 20428 KB Output is correct
50 Correct 218 ms 36296 KB Output is correct
51 Correct 1618 ms 119356 KB Output is correct
52 Correct 376 ms 101008 KB Output is correct
53 Correct 9 ms 2396 KB Output is correct
54 Correct 1071 ms 39464 KB Output is correct
55 Correct 942 ms 43816 KB Output is correct
56 Correct 1599 ms 203416 KB Output is correct
57 Correct 755 ms 48836 KB Output is correct
58 Correct 763 ms 49092 KB Output is correct
59 Correct 708 ms 48408 KB Output is correct
60 Correct 732 ms 48584 KB Output is correct
61 Correct 784 ms 48788 KB Output is correct
62 Correct 403 ms 23948 KB Output is correct
63 Correct 18 ms 5212 KB Output is correct
64 Correct 447 ms 35272 KB Output is correct
65 Correct 363 ms 36296 KB Output is correct
66 Correct 425 ms 67016 KB Output is correct
67 Correct 258 ms 33996 KB Output is correct
68 Correct 536 ms 118620 KB Output is correct
69 Correct 1538 ms 176428 KB Output is correct
70 Correct 501 ms 36040 KB Output is correct
71 Correct 1965 ms 110876 KB Output is correct
72 Correct 227 ms 20684 KB Output is correct
73 Correct 1580 ms 119588 KB Output is correct
74 Correct 268 ms 52820 KB Output is correct
75 Correct 288 ms 52424 KB Output is correct
76 Correct 408 ms 62668 KB Output is correct
77 Correct 321 ms 24336 KB Output is correct
78 Correct 175 ms 16840 KB Output is correct
79 Correct 67 ms 9936 KB Output is correct
80 Correct 63 ms 11732 KB Output is correct
81 Correct 492 ms 102216 KB Output is correct
82 Correct 147 ms 18636 KB Output is correct
83 Correct 74 ms 10440 KB Output is correct
84 Correct 50 ms 13908 KB Output is correct
85 Execution timed out 4102 ms 927016 KB Time limit exceeded
86 Halted 0 ms 0 KB -