oj.uz

Submission #1071603

# Submission time Handle Problem Language Result Execution time Memory
1071603 2024-08-23T09:16:42 Z Gromp15 Sky Walking (IOI19_walk) C++17
24 / 100
 4000 ms 682888 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];
	}
	*/
	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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 348 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 0 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 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 1 ms 604 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1199 ms 140360 KB Output is correct
4 Correct 771 ms 157168 KB Output is correct
5 Correct 346 ms 100084 KB Output is correct
6 Correct 300 ms 89620 KB Output is correct
7 Correct 355 ms 99832 KB Output is correct
8 Correct 1687 ms 180132 KB Output is correct
9 Correct 453 ms 102904 KB Output is correct
10 Correct 1096 ms 216304 KB Output is correct
11 Correct 374 ms 77064 KB Output is correct
12 Correct 237 ms 60160 KB Output is correct
13 Correct 857 ms 193324 KB Output is correct
14 Correct 145 ms 46088 KB Output is correct
15 Correct 200 ms 60284 KB Output is correct
16 Correct 217 ms 60364 KB Output is correct
17 Correct 204 ms 58428 KB Output is correct
18 Correct 348 ms 56076 KB Output is correct
19 Correct 6 ms 3160 KB Output is correct
20 Correct 65 ms 29168 KB Output is correct
21 Correct 202 ms 54728 KB Output is correct
22 Correct 190 ms 60176 KB Output is correct
23 Correct 265 ms 71180 KB Output is correct
24 Correct 202 ms 59652 KB Output is correct
25 Correct 186 ms 57724 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 15532 KB Output is correct
2 Execution timed out 4054 ms 682888 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 15532 KB Output is correct
2 Execution timed out 4054 ms 682888 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 348 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 0 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 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 1 ms 604 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1199 ms 140360 KB Output is correct
21 Correct 771 ms 157168 KB Output is correct
22 Correct 346 ms 100084 KB Output is correct
23 Correct 300 ms 89620 KB Output is correct
24 Correct 355 ms 99832 KB Output is correct
25 Correct 1687 ms 180132 KB Output is correct
26 Correct 453 ms 102904 KB Output is correct
27 Correct 1096 ms 216304 KB Output is correct
28 Correct 374 ms 77064 KB Output is correct
29 Correct 237 ms 60160 KB Output is correct
30 Correct 857 ms 193324 KB Output is correct
31 Correct 145 ms 46088 KB Output is correct
32 Correct 200 ms 60284 KB Output is correct
33 Correct 217 ms 60364 KB Output is correct
34 Correct 204 ms 58428 KB Output is correct
35 Correct 348 ms 56076 KB Output is correct
36 Correct 6 ms 3160 KB Output is correct
37 Correct 65 ms 29168 KB Output is correct
38 Correct 202 ms 54728 KB Output is correct
39 Correct 190 ms 60176 KB Output is correct
40 Correct 265 ms 71180 KB Output is correct
41 Correct 202 ms 59652 KB Output is correct
42 Correct 186 ms 57724 KB Output is correct
43 Correct 52 ms 15532 KB Output is correct
44 Execution timed out 4054 ms 682888 KB Time limit exceeded
45 Halted 0 ms 0 KB -