oj.uz

Submission #932221

# Submission time Handle Problem Language Result Execution time Memory
932221 2024-02-23T05:43:36 Z siewjh Sky Walking (IOI19_walk) C++17
24 / 100
 945 ms 257220 KB 
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100005;
const int MAXND = 1000005;
int hv[MAXN], ind = -1;
vector<int> add;
map<int, int> mp[MAXN];
vector<pair<int, ll>> adj[MAXND];
ll dist[MAXND];
struct node{
	int s, e, m; vector<pair<int, int>> vec;
	node *l, *r;
	node (int _s, int _e){
		s = _s, e = _e, m = (s + e) >> 1;
		if (s == e) vec.push_back({hv[s], s});
		else{
			l = new node(s, m); r = new node(m + 1, e);
			auto &lv = l->vec, &rv = r->vec;
			int lind = 0, lsz = lv.size(), rind = 0, rsz = rv.size();
			while (lind < lsz && rind < rsz){
				if (lv[lind].first >= rv[rind].first){
					vec.push_back(lv[lind]);
					lind++;
				}
				else{
					vec.push_back(rv[rind]);
					rind++;
				}
			}
			while (lind < lsz){
				vec.push_back(lv[lind]);
				lind++;
			}
			while (rind < rsz){
				vec.push_back(rv[rind]);
				rind++;
			}
		}
	}
	void query(int x, int y, int h){
		if (x == s && y == e){
			int sz = e - s + 1;
			for (int i = 0; i < sz && vec[i].first >= h; i++) add.push_back(vec[i].second);
			return;
		}
		else if (y <= m) l->query(x, y, h);
		else if (x > m) r->query(x, y, h);
		else{
			l->query(x, m, h); r->query(m + 1, y, h);
		}
	}
};

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g){
	int n = x.size(), m = y.size();
	for (int i = 0; i < n; i++) hv[i] = h[i];
	node *root = new node(0, n - 1);
	mp[s][0] = ++ind; mp[g][0] = ++ind;
	for (int i = 0; i < m; i++){
		add.clear();
		root->query(l[i], r[i], y[i]);
		sort(add.begin(), add.end());
		int prev = -1, px;
		for (int b : add){
			int aind;
			if (mp[b].count(y[i])) aind = mp[b][y[i]];
			else mp[b][y[i]] = aind = ++ind;
			if (prev != -1){
				adj[aind].push_back({prev, x[b] - px});
				adj[prev].push_back({aind, x[b] - px});
			}
			prev = aind; px = x[b];
		}
	}
	for (int i = 0; i < n; i++){
		int prev = -1, ph;
		for (auto &[height, aind] : mp[i]){
			if (prev != -1){
				adj[aind].push_back({prev, height - ph});
				adj[prev].push_back({aind, height - ph});
			}
			prev = aind; ph = height;
		}
	}
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
	pq.push({0, 0});
	for (int i = 0; i <= ind; i++) dist[i] = 1e18;
	dist[0] = 0;
	while (!pq.empty()){
		ll d; int i; tie(d, i) = pq.top(); pq.pop();
		if (dist[i] != d) continue;
		if (i == 1) return d;
		for (auto &[nn, nd] : adj[i]){
			if (d + nd < dist[nn]){
				dist[nn] = d + nd;
				pq.push({dist[nn], nn});
			}
		}
	}
	return -1;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 30128 KB Output is correct
2 Correct 7 ms 30044 KB Output is correct
3 Correct 8 ms 30040 KB Output is correct
4 Correct 7 ms 30044 KB Output is correct
5 Correct 7 ms 30044 KB Output is correct
6 Correct 7 ms 30044 KB Output is correct
7 Correct 8 ms 30040 KB Output is correct
8 Correct 7 ms 30044 KB Output is correct
9 Correct 7 ms 30096 KB Output is correct
10 Correct 8 ms 30132 KB Output is correct
11 Correct 7 ms 30296 KB Output is correct
12 Correct 7 ms 30044 KB Output is correct
13 Correct 8 ms 30044 KB Output is correct
14 Correct 7 ms 30044 KB Output is correct
15 Correct 7 ms 30044 KB Output is correct
16 Correct 8 ms 30044 KB Output is correct
17 Correct 7 ms 30044 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 30128 KB Output is correct
2 Correct 7 ms 30044 KB Output is correct
3 Correct 607 ms 153472 KB Output is correct
4 Correct 665 ms 183356 KB Output is correct
5 Correct 432 ms 167960 KB Output is correct
6 Correct 403 ms 152484 KB Output is correct
7 Correct 420 ms 167844 KB Output is correct
8 Correct 823 ms 188004 KB Output is correct
9 Correct 515 ms 161616 KB Output is correct
10 Correct 945 ms 235984 KB Output is correct
11 Correct 310 ms 103624 KB Output is correct
12 Correct 244 ms 93892 KB Output is correct
13 Correct 770 ms 212168 KB Output is correct
14 Correct 236 ms 93384 KB Output is correct
15 Correct 262 ms 93124 KB Output is correct
16 Correct 262 ms 93172 KB Output is correct
17 Correct 234 ms 91588 KB Output is correct
18 Correct 288 ms 105536 KB Output is correct
19 Correct 13 ms 32856 KB Output is correct
20 Correct 68 ms 61516 KB Output is correct
21 Correct 215 ms 87236 KB Output is correct
22 Correct 210 ms 92852 KB Output is correct
23 Correct 311 ms 106244 KB Output is correct
24 Correct 255 ms 92444 KB Output is correct
25 Correct 233 ms 91072 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 46672 KB Output is correct
2 Runtime error 465 ms 257220 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 46672 KB Output is correct
2 Runtime error 465 ms 257220 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 30128 KB Output is correct
2 Correct 7 ms 30044 KB Output is correct
3 Correct 8 ms 30040 KB Output is correct
4 Correct 7 ms 30044 KB Output is correct
5 Correct 7 ms 30044 KB Output is correct
6 Correct 7 ms 30044 KB Output is correct
7 Correct 8 ms 30040 KB Output is correct
8 Correct 7 ms 30044 KB Output is correct
9 Correct 7 ms 30096 KB Output is correct
10 Correct 8 ms 30132 KB Output is correct
11 Correct 7 ms 30296 KB Output is correct
12 Correct 7 ms 30044 KB Output is correct
13 Correct 8 ms 30044 KB Output is correct
14 Correct 7 ms 30044 KB Output is correct
15 Correct 7 ms 30044 KB Output is correct
16 Correct 8 ms 30044 KB Output is correct
17 Correct 7 ms 30044 KB Output is correct
18 Correct 8 ms 30128 KB Output is correct
19 Correct 7 ms 30044 KB Output is correct
20 Correct 607 ms 153472 KB Output is correct
21 Correct 665 ms 183356 KB Output is correct
22 Correct 432 ms 167960 KB Output is correct
23 Correct 403 ms 152484 KB Output is correct
24 Correct 420 ms 167844 KB Output is correct
25 Correct 823 ms 188004 KB Output is correct
26 Correct 515 ms 161616 KB Output is correct
27 Correct 945 ms 235984 KB Output is correct
28 Correct 310 ms 103624 KB Output is correct
29 Correct 244 ms 93892 KB Output is correct
30 Correct 770 ms 212168 KB Output is correct
31 Correct 236 ms 93384 KB Output is correct
32 Correct 262 ms 93124 KB Output is correct
33 Correct 262 ms 93172 KB Output is correct
34 Correct 234 ms 91588 KB Output is correct
35 Correct 288 ms 105536 KB Output is correct
36 Correct 13 ms 32856 KB Output is correct
37 Correct 68 ms 61516 KB Output is correct
38 Correct 215 ms 87236 KB Output is correct
39 Correct 210 ms 92852 KB Output is correct
40 Correct 311 ms 106244 KB Output is correct
41 Correct 255 ms 92444 KB Output is correct
42 Correct 233 ms 91072 KB Output is correct
43 Correct 63 ms 46672 KB Output is correct
44 Runtime error 465 ms 257220 KB Execution killed with signal 6
45 Halted 0 ms 0 KB -