oj.uz

Submission #607485

# Submission time Handle Problem Language Result Execution time Memory
607485 2022-07-26T18:18:56 Z Temmie Sky Walking (IOI19_walk) C++17
57 / 100
 829 ms 109768 KB 
#include <bits/stdc++.h>

struct SG {
	
	int h, l, r;
	
	SG() { }
	
	SG(int a, int b, int c) : h(a) , l(b) , r(c) { }
	
	friend std::ostream& operator << (std::ostream& stream, const SG& sg) {
		return stream << "(" << sg.l << " " << sg.r << " " << sg.h << ")";
	}
	
};

int n, m;
std::vector <std::pair <int, int>> g[2];
std::vector <std::vector <std::pair <int, int>>> gg;
std::vector <std::vector <int>> del[2];
std::vector <int> h;
std::vector <SG> sg;

void fix(int node) {
	std::vector <std::pair <int, int>> dir[2];
	dir[0] = dir[1] = { { h[node], node } };
	for (int i = node + 1; i < n; i++) {
		if (h[i] <= dir[1].back().first) {
			continue;
		}
		dir[1].emplace_back(h[i], i);
	}
	for (int i = node - 1; i >= 0; i--) {
		if (h[i] <= dir[0].back().first) {
			continue;
		}
		dir[0].emplace_back(h[i], i);
	}
	auto cop = sg;
	cop.clear();
	for (const auto& s : sg) {
		if (s.l < node && node < s.r) {
			int lb[2] = {
				(int) (std::lower_bound(dir[0].begin(), dir[0].end(), std::make_pair(s.h, -1)) - dir[0].begin()),
				(int) (std::lower_bound(dir[1].begin(), dir[1].end(), std::make_pair(s.h, -1)) - dir[1].begin())
			};
			if (s.l != dir[0][lb[0]].second) {
				cop.emplace_back(s.h, s.l, dir[0][lb[0]].second);
			}
			if (dir[0][lb[0]].second != dir[1][lb[1]].second) {
				cop.emplace_back(s.h, dir[0][lb[0]].second, dir[1][lb[1]].second);
			}
			if (dir[1][lb[1]].second != s.r) {
				cop.emplace_back(s.h, dir[1][lb[1]].second, s.r);
			}
		} else {
			cop.emplace_back(s);
		}
	}
	sg = cop;
}

long long min_distance(std::vector <int> a, std::vector <int> _h, std::vector <int> l, std::vector <int> r, std::vector <int> y, int f, int t) {
	n = a.size();
	m = l.size();
	sg.resize(m);
	h = _h;
	for (int i = 0; i < m; i++) {
		sg[i] = { y[i], l[i], r[i] };
	}
	fix(f);
	fix(t);
	del[0].resize(400'000);
	del[1].resize(400'000);
	for (const auto& s : sg) {
		del[0][s.l].emplace_back(s.h);
		del[1][s.r].emplace_back(s.h);
	}
	std::multiset <int> st = { 0 };
	for (int i = 0; i < n; i++) {
		for (int x : del[0][i]) {
			st.insert(x);
		}
		for (int k = 0; k < 2; k++) {
			for (int x : del[k][i]) {
				g[0].emplace_back(a[i], x);
				g[0].emplace_back(a[i], *prev(st.lower_bound(x)));
			}
		}
		for (int x : del[1][i]) {
			st.erase(st.find(x));
		}
	}
	std::sort(g[0].begin(), g[0].end());
	for (auto p : g[0]) {
		if (g[1].empty() || g[1].back() != p) {
			g[1].push_back(p);
		}
	}
	g[0] = g[1];
	g[1].clear();
	for (auto p : g[0]) {
		g[1].emplace_back(p.second, p.first);
	}
	std::sort(g[1].begin(), g[1].end());
	gg.resize(400'000);
	for (int i = 1; i < (int) g[0].size(); i++) {
		if (g[0][i - 1].first != g[0][i].first) {
			continue;
		}
		gg[i - 1].emplace_back(i - 0, g[0][i].second - g[0][i - 1].second);
		gg[i - 0].emplace_back(i - 1, g[0][i].second - g[0][i - 1].second);
	}
	for (const auto& s : sg) {
		int lb = std::lower_bound(g[1].begin(), g[1].end(), std::make_pair(s.h, a[s.l])) - g[1].begin();
		while (g[1][lb] != (std::pair <int, int>) { s.h, a[s.r] }) {
			std::pair <int, int> p[2] = {
				{ g[1][lb - 0].second, g[1][lb - 0].first },
				{ g[1][lb + 1].second, g[1][lb + 1].first }
			};
			lb++;
			gg[std::lower_bound(g[0].begin(), g[0].end(), p[0]) - g[0].begin()].emplace_back(std::lower_bound(g[0].begin(), g[0].end(), p[1]) - g[0].begin(), p[1].first - p[0].first);
			gg[std::lower_bound(g[0].begin(), g[0].end(), p[1]) - g[0].begin()].emplace_back(std::lower_bound(g[0].begin(), g[0].end(), p[0]) - g[0].begin(), p[1].first - p[0].first);
		}
	}
	std::vector <long long> dd(400'000, 1LL << 60);
	std::priority_queue <std::pair <long long, int>> pq;
	{
		int tmp = std::lower_bound(g[0].begin(), g[0].end(), std::make_pair(a[f], 0)) - g[0].begin();
		if (tmp == (int) g[0].size() || g[0][tmp] != (std::pair <int, int>) { a[f], 0 }) {
			return -1;
		}
		pq.push({ dd[tmp] = 0, tmp });
	}
	while (pq.size()) {
		int v = pq.top().second;
		pq.pop();
		for (auto p : gg[v]) {
			if (dd[p.first] <= dd[v] + p.second) {
				continue;
			}
			dd[p.first] = dd[v] + p.second;
			pq.push({ -dd[p.first], p.first });
		}
	}
	int lb = std::lower_bound(g[0].begin(), g[0].end(), std::make_pair(a[t], 0)) - g[0].begin();
	return lb == (int) g[0].size() || g[0][lb] != (std::pair <int, int>) { a[t], 0 } || dd[lb] == (1LL << 60) ? -1LL : dd[lb];
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 31572 KB Output is correct
2 Correct 20 ms 31524 KB Output is correct
3 Correct 18 ms 31576 KB Output is correct
4 Correct 20 ms 31528 KB Output is correct
5 Correct 20 ms 31608 KB Output is correct
6 Correct 20 ms 31528 KB Output is correct
7 Correct 18 ms 31572 KB Output is correct
8 Correct 18 ms 31572 KB Output is correct
9 Correct 19 ms 31528 KB Output is correct
10 Correct 19 ms 31540 KB Output is correct
11 Correct 17 ms 31572 KB Output is correct
12 Correct 16 ms 31564 KB Output is correct
13 Correct 21 ms 31528 KB Output is correct
14 Correct 21 ms 31536 KB Output is correct
15 Correct 19 ms 31528 KB Output is correct
16 Correct 30 ms 31516 KB Output is correct
17 Correct 21 ms 31600 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 31532 KB Output is correct
2 Correct 18 ms 31572 KB Output is correct
3 Correct 543 ms 63120 KB Output is correct
4 Correct 583 ms 69672 KB Output is correct
5 Correct 330 ms 60728 KB Output is correct
6 Correct 347 ms 60128 KB Output is correct
7 Correct 330 ms 60832 KB Output is correct
8 Correct 606 ms 64256 KB Output is correct
9 Correct 476 ms 66460 KB Output is correct
10 Correct 539 ms 68784 KB Output is correct
11 Correct 493 ms 61932 KB Output is correct
12 Correct 341 ms 66912 KB Output is correct
13 Correct 552 ms 71552 KB Output is correct
14 Correct 340 ms 61200 KB Output is correct
15 Correct 379 ms 64636 KB Output is correct
16 Correct 327 ms 63448 KB Output is correct
17 Correct 344 ms 62348 KB Output is correct
18 Correct 519 ms 60480 KB Output is correct
19 Correct 32 ms 33076 KB Output is correct
20 Correct 125 ms 46940 KB Output is correct
21 Correct 358 ms 61524 KB Output is correct
22 Correct 336 ms 66164 KB Output is correct
23 Correct 460 ms 66256 KB Output is correct
24 Correct 364 ms 64584 KB Output is correct
25 Correct 303 ms 62140 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 40644 KB Output is correct
2 Correct 665 ms 66320 KB Output is correct
3 Correct 662 ms 67476 KB Output is correct
4 Correct 785 ms 72828 KB Output is correct
5 Correct 829 ms 74292 KB Output is correct
6 Correct 806 ms 72020 KB Output is correct
7 Correct 324 ms 55060 KB Output is correct
8 Correct 371 ms 66868 KB Output is correct
9 Correct 707 ms 72596 KB Output is correct
10 Correct 388 ms 62644 KB Output is correct
11 Correct 29 ms 33364 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 40644 KB Output is correct
2 Correct 665 ms 66320 KB Output is correct
3 Correct 662 ms 67476 KB Output is correct
4 Correct 785 ms 72828 KB Output is correct
5 Correct 829 ms 74292 KB Output is correct
6 Correct 806 ms 72020 KB Output is correct
7 Correct 324 ms 55060 KB Output is correct
8 Correct 371 ms 66868 KB Output is correct
9 Correct 707 ms 72596 KB Output is correct
10 Correct 388 ms 62644 KB Output is correct
11 Correct 29 ms 33364 KB Output is correct
12 Correct 689 ms 67596 KB Output is correct
13 Correct 617 ms 71756 KB Output is correct
14 Correct 813 ms 74144 KB Output is correct
15 Correct 606 ms 71076 KB Output is correct
16 Correct 576 ms 67960 KB Output is correct
17 Correct 662 ms 71612 KB Output is correct
18 Correct 589 ms 71144 KB Output is correct
19 Correct 567 ms 67828 KB Output is correct
20 Correct 342 ms 54144 KB Output is correct
21 Correct 60 ms 35808 KB Output is correct
22 Correct 466 ms 64260 KB Output is correct
23 Correct 425 ms 64064 KB Output is correct
24 Correct 329 ms 61324 KB Output is correct
25 Correct 405 ms 62668 KB Output is correct
26 Correct 313 ms 61272 KB Output is correct
27 Correct 786 ms 74416 KB Output is correct
28 Correct 588 ms 71772 KB Output is correct
29 Correct 764 ms 71860 KB Output is correct
30 Correct 392 ms 55140 KB Output is correct
31 Correct 708 ms 72460 KB Output is correct
32 Correct 341 ms 62080 KB Output is correct
33 Correct 337 ms 64296 KB Output is correct
34 Correct 424 ms 63920 KB Output is correct
35 Correct 415 ms 65344 KB Output is correct
36 Correct 346 ms 63212 KB Output is correct
37 Correct 294 ms 61460 KB Output is correct
38 Correct 299 ms 66080 KB Output is correct
39 Correct 414 ms 66364 KB Output is correct
40 Correct 369 ms 64528 KB Output is correct
41 Correct 332 ms 62132 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 31572 KB Output is correct
2 Correct 20 ms 31524 KB Output is correct
3 Correct 18 ms 31576 KB Output is correct
4 Correct 20 ms 31528 KB Output is correct
5 Correct 20 ms 31608 KB Output is correct
6 Correct 20 ms 31528 KB Output is correct
7 Correct 18 ms 31572 KB Output is correct
8 Correct 18 ms 31572 KB Output is correct
9 Correct 19 ms 31528 KB Output is correct
10 Correct 19 ms 31540 KB Output is correct
11 Correct 17 ms 31572 KB Output is correct
12 Correct 16 ms 31564 KB Output is correct
13 Correct 21 ms 31528 KB Output is correct
14 Correct 21 ms 31536 KB Output is correct
15 Correct 19 ms 31528 KB Output is correct
16 Correct 30 ms 31516 KB Output is correct
17 Correct 21 ms 31600 KB Output is correct
18 Correct 16 ms 31532 KB Output is correct
19 Correct 18 ms 31572 KB Output is correct
20 Correct 543 ms 63120 KB Output is correct
21 Correct 583 ms 69672 KB Output is correct
22 Correct 330 ms 60728 KB Output is correct
23 Correct 347 ms 60128 KB Output is correct
24 Correct 330 ms 60832 KB Output is correct
25 Correct 606 ms 64256 KB Output is correct
26 Correct 476 ms 66460 KB Output is correct
27 Correct 539 ms 68784 KB Output is correct
28 Correct 493 ms 61932 KB Output is correct
29 Correct 341 ms 66912 KB Output is correct
30 Correct 552 ms 71552 KB Output is correct
31 Correct 340 ms 61200 KB Output is correct
32 Correct 379 ms 64636 KB Output is correct
33 Correct 327 ms 63448 KB Output is correct
34 Correct 344 ms 62348 KB Output is correct
35 Correct 519 ms 60480 KB Output is correct
36 Correct 32 ms 33076 KB Output is correct
37 Correct 125 ms 46940 KB Output is correct
38 Correct 358 ms 61524 KB Output is correct
39 Correct 336 ms 66164 KB Output is correct
40 Correct 460 ms 66256 KB Output is correct
41 Correct 364 ms 64584 KB Output is correct
42 Correct 303 ms 62140 KB Output is correct
43 Correct 135 ms 40644 KB Output is correct
44 Correct 665 ms 66320 KB Output is correct
45 Correct 662 ms 67476 KB Output is correct
46 Correct 785 ms 72828 KB Output is correct
47 Correct 829 ms 74292 KB Output is correct
48 Correct 806 ms 72020 KB Output is correct
49 Correct 324 ms 55060 KB Output is correct
50 Correct 371 ms 66868 KB Output is correct
51 Correct 707 ms 72596 KB Output is correct
52 Correct 388 ms 62644 KB Output is correct
53 Correct 29 ms 33364 KB Output is correct
54 Correct 689 ms 67596 KB Output is correct
55 Correct 617 ms 71756 KB Output is correct
56 Correct 813 ms 74144 KB Output is correct
57 Correct 606 ms 71076 KB Output is correct
58 Correct 576 ms 67960 KB Output is correct
59 Correct 662 ms 71612 KB Output is correct
60 Correct 589 ms 71144 KB Output is correct
61 Correct 567 ms 67828 KB Output is correct
62 Correct 342 ms 54144 KB Output is correct
63 Correct 60 ms 35808 KB Output is correct
64 Correct 466 ms 64260 KB Output is correct
65 Correct 425 ms 64064 KB Output is correct
66 Correct 329 ms 61324 KB Output is correct
67 Correct 405 ms 62668 KB Output is correct
68 Correct 313 ms 61272 KB Output is correct
69 Correct 786 ms 74416 KB Output is correct
70 Correct 588 ms 71772 KB Output is correct
71 Correct 764 ms 71860 KB Output is correct
72 Correct 392 ms 55140 KB Output is correct
73 Correct 708 ms 72460 KB Output is correct
74 Correct 341 ms 62080 KB Output is correct
75 Correct 337 ms 64296 KB Output is correct
76 Correct 424 ms 63920 KB Output is correct
77 Correct 415 ms 65344 KB Output is correct
78 Correct 346 ms 63212 KB Output is correct
79 Correct 294 ms 61460 KB Output is correct
80 Correct 299 ms 66080 KB Output is correct
81 Correct 414 ms 66364 KB Output is correct
82 Correct 369 ms 64528 KB Output is correct
83 Correct 332 ms 62132 KB Output is correct
84 Correct 106 ms 39068 KB Output is correct
85 Runtime error 295 ms 109768 KB Execution killed with signal 11
86 Halted 0 ms 0 KB -