# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
607494 |
2022-07-26T18:38:28 Z |
Temmie |
Sky Walking (IOI19_walk) |
C++17 |
|
823 ms |
107772 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) { }
};
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());
g[0].resize(std::unique(g[0].begin(), g[0].end()) - g[0].begin());
//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];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
31572 KB |
Output is correct |
2 |
Correct |
14 ms |
31612 KB |
Output is correct |
3 |
Correct |
16 ms |
31532 KB |
Output is correct |
4 |
Correct |
15 ms |
31600 KB |
Output is correct |
5 |
Correct |
15 ms |
31524 KB |
Output is correct |
6 |
Correct |
15 ms |
31628 KB |
Output is correct |
7 |
Correct |
16 ms |
31572 KB |
Output is correct |
8 |
Correct |
15 ms |
31560 KB |
Output is correct |
9 |
Correct |
15 ms |
31572 KB |
Output is correct |
10 |
Correct |
17 ms |
31616 KB |
Output is correct |
11 |
Correct |
17 ms |
31508 KB |
Output is correct |
12 |
Correct |
15 ms |
31572 KB |
Output is correct |
13 |
Correct |
17 ms |
31572 KB |
Output is correct |
14 |
Correct |
16 ms |
31556 KB |
Output is correct |
15 |
Correct |
16 ms |
31572 KB |
Output is correct |
16 |
Correct |
20 ms |
31616 KB |
Output is correct |
17 |
Correct |
15 ms |
31572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
31572 KB |
Output is correct |
2 |
Correct |
15 ms |
31572 KB |
Output is correct |
3 |
Correct |
485 ms |
60984 KB |
Output is correct |
4 |
Correct |
455 ms |
65756 KB |
Output is correct |
5 |
Correct |
301 ms |
57288 KB |
Output is correct |
6 |
Correct |
291 ms |
56588 KB |
Output is correct |
7 |
Correct |
302 ms |
57268 KB |
Output is correct |
8 |
Correct |
503 ms |
62136 KB |
Output is correct |
9 |
Correct |
423 ms |
63032 KB |
Output is correct |
10 |
Correct |
511 ms |
64984 KB |
Output is correct |
11 |
Correct |
427 ms |
59120 KB |
Output is correct |
12 |
Correct |
293 ms |
62948 KB |
Output is correct |
13 |
Correct |
473 ms |
67484 KB |
Output is correct |
14 |
Correct |
292 ms |
57440 KB |
Output is correct |
15 |
Correct |
301 ms |
61264 KB |
Output is correct |
16 |
Correct |
304 ms |
60552 KB |
Output is correct |
17 |
Correct |
287 ms |
59660 KB |
Output is correct |
18 |
Correct |
408 ms |
58036 KB |
Output is correct |
19 |
Correct |
23 ms |
32860 KB |
Output is correct |
20 |
Correct |
102 ms |
45152 KB |
Output is correct |
21 |
Correct |
295 ms |
58736 KB |
Output is correct |
22 |
Correct |
283 ms |
62916 KB |
Output is correct |
23 |
Correct |
404 ms |
63484 KB |
Output is correct |
24 |
Correct |
298 ms |
61532 KB |
Output is correct |
25 |
Correct |
286 ms |
59528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
104 ms |
39888 KB |
Output is correct |
2 |
Correct |
599 ms |
64596 KB |
Output is correct |
3 |
Correct |
617 ms |
65396 KB |
Output is correct |
4 |
Correct |
662 ms |
68820 KB |
Output is correct |
5 |
Correct |
823 ms |
70344 KB |
Output is correct |
6 |
Correct |
683 ms |
68080 KB |
Output is correct |
7 |
Correct |
290 ms |
52180 KB |
Output is correct |
8 |
Correct |
301 ms |
62940 KB |
Output is correct |
9 |
Correct |
662 ms |
68656 KB |
Output is correct |
10 |
Correct |
329 ms |
59312 KB |
Output is correct |
11 |
Correct |
26 ms |
32592 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
104 ms |
39888 KB |
Output is correct |
2 |
Correct |
599 ms |
64596 KB |
Output is correct |
3 |
Correct |
617 ms |
65396 KB |
Output is correct |
4 |
Correct |
662 ms |
68820 KB |
Output is correct |
5 |
Correct |
823 ms |
70344 KB |
Output is correct |
6 |
Correct |
683 ms |
68080 KB |
Output is correct |
7 |
Correct |
290 ms |
52180 KB |
Output is correct |
8 |
Correct |
301 ms |
62940 KB |
Output is correct |
9 |
Correct |
662 ms |
68656 KB |
Output is correct |
10 |
Correct |
329 ms |
59312 KB |
Output is correct |
11 |
Correct |
26 ms |
32592 KB |
Output is correct |
12 |
Correct |
622 ms |
65288 KB |
Output is correct |
13 |
Correct |
594 ms |
67768 KB |
Output is correct |
14 |
Correct |
748 ms |
70244 KB |
Output is correct |
15 |
Correct |
572 ms |
67324 KB |
Output is correct |
16 |
Correct |
482 ms |
63884 KB |
Output is correct |
17 |
Correct |
550 ms |
67636 KB |
Output is correct |
18 |
Correct |
540 ms |
67380 KB |
Output is correct |
19 |
Correct |
522 ms |
64032 KB |
Output is correct |
20 |
Correct |
346 ms |
51164 KB |
Output is correct |
21 |
Correct |
42 ms |
33824 KB |
Output is correct |
22 |
Correct |
444 ms |
60588 KB |
Output is correct |
23 |
Correct |
373 ms |
60248 KB |
Output is correct |
24 |
Correct |
303 ms |
57588 KB |
Output is correct |
25 |
Correct |
341 ms |
58920 KB |
Output is correct |
26 |
Correct |
263 ms |
57504 KB |
Output is correct |
27 |
Correct |
708 ms |
70452 KB |
Output is correct |
28 |
Correct |
551 ms |
67704 KB |
Output is correct |
29 |
Correct |
720 ms |
67964 KB |
Output is correct |
30 |
Correct |
286 ms |
52184 KB |
Output is correct |
31 |
Correct |
629 ms |
68424 KB |
Output is correct |
32 |
Correct |
305 ms |
58964 KB |
Output is correct |
33 |
Correct |
308 ms |
61064 KB |
Output is correct |
34 |
Correct |
355 ms |
60808 KB |
Output is correct |
35 |
Correct |
355 ms |
62128 KB |
Output is correct |
36 |
Correct |
327 ms |
60292 KB |
Output is correct |
37 |
Correct |
297 ms |
58780 KB |
Output is correct |
38 |
Correct |
288 ms |
62964 KB |
Output is correct |
39 |
Correct |
385 ms |
63420 KB |
Output is correct |
40 |
Correct |
298 ms |
61540 KB |
Output is correct |
41 |
Correct |
281 ms |
59340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
31572 KB |
Output is correct |
2 |
Correct |
14 ms |
31612 KB |
Output is correct |
3 |
Correct |
16 ms |
31532 KB |
Output is correct |
4 |
Correct |
15 ms |
31600 KB |
Output is correct |
5 |
Correct |
15 ms |
31524 KB |
Output is correct |
6 |
Correct |
15 ms |
31628 KB |
Output is correct |
7 |
Correct |
16 ms |
31572 KB |
Output is correct |
8 |
Correct |
15 ms |
31560 KB |
Output is correct |
9 |
Correct |
15 ms |
31572 KB |
Output is correct |
10 |
Correct |
17 ms |
31616 KB |
Output is correct |
11 |
Correct |
17 ms |
31508 KB |
Output is correct |
12 |
Correct |
15 ms |
31572 KB |
Output is correct |
13 |
Correct |
17 ms |
31572 KB |
Output is correct |
14 |
Correct |
16 ms |
31556 KB |
Output is correct |
15 |
Correct |
16 ms |
31572 KB |
Output is correct |
16 |
Correct |
20 ms |
31616 KB |
Output is correct |
17 |
Correct |
15 ms |
31572 KB |
Output is correct |
18 |
Correct |
16 ms |
31572 KB |
Output is correct |
19 |
Correct |
15 ms |
31572 KB |
Output is correct |
20 |
Correct |
485 ms |
60984 KB |
Output is correct |
21 |
Correct |
455 ms |
65756 KB |
Output is correct |
22 |
Correct |
301 ms |
57288 KB |
Output is correct |
23 |
Correct |
291 ms |
56588 KB |
Output is correct |
24 |
Correct |
302 ms |
57268 KB |
Output is correct |
25 |
Correct |
503 ms |
62136 KB |
Output is correct |
26 |
Correct |
423 ms |
63032 KB |
Output is correct |
27 |
Correct |
511 ms |
64984 KB |
Output is correct |
28 |
Correct |
427 ms |
59120 KB |
Output is correct |
29 |
Correct |
293 ms |
62948 KB |
Output is correct |
30 |
Correct |
473 ms |
67484 KB |
Output is correct |
31 |
Correct |
292 ms |
57440 KB |
Output is correct |
32 |
Correct |
301 ms |
61264 KB |
Output is correct |
33 |
Correct |
304 ms |
60552 KB |
Output is correct |
34 |
Correct |
287 ms |
59660 KB |
Output is correct |
35 |
Correct |
408 ms |
58036 KB |
Output is correct |
36 |
Correct |
23 ms |
32860 KB |
Output is correct |
37 |
Correct |
102 ms |
45152 KB |
Output is correct |
38 |
Correct |
295 ms |
58736 KB |
Output is correct |
39 |
Correct |
283 ms |
62916 KB |
Output is correct |
40 |
Correct |
404 ms |
63484 KB |
Output is correct |
41 |
Correct |
298 ms |
61532 KB |
Output is correct |
42 |
Correct |
286 ms |
59528 KB |
Output is correct |
43 |
Correct |
104 ms |
39888 KB |
Output is correct |
44 |
Correct |
599 ms |
64596 KB |
Output is correct |
45 |
Correct |
617 ms |
65396 KB |
Output is correct |
46 |
Correct |
662 ms |
68820 KB |
Output is correct |
47 |
Correct |
823 ms |
70344 KB |
Output is correct |
48 |
Correct |
683 ms |
68080 KB |
Output is correct |
49 |
Correct |
290 ms |
52180 KB |
Output is correct |
50 |
Correct |
301 ms |
62940 KB |
Output is correct |
51 |
Correct |
662 ms |
68656 KB |
Output is correct |
52 |
Correct |
329 ms |
59312 KB |
Output is correct |
53 |
Correct |
26 ms |
32592 KB |
Output is correct |
54 |
Correct |
622 ms |
65288 KB |
Output is correct |
55 |
Correct |
594 ms |
67768 KB |
Output is correct |
56 |
Correct |
748 ms |
70244 KB |
Output is correct |
57 |
Correct |
572 ms |
67324 KB |
Output is correct |
58 |
Correct |
482 ms |
63884 KB |
Output is correct |
59 |
Correct |
550 ms |
67636 KB |
Output is correct |
60 |
Correct |
540 ms |
67380 KB |
Output is correct |
61 |
Correct |
522 ms |
64032 KB |
Output is correct |
62 |
Correct |
346 ms |
51164 KB |
Output is correct |
63 |
Correct |
42 ms |
33824 KB |
Output is correct |
64 |
Correct |
444 ms |
60588 KB |
Output is correct |
65 |
Correct |
373 ms |
60248 KB |
Output is correct |
66 |
Correct |
303 ms |
57588 KB |
Output is correct |
67 |
Correct |
341 ms |
58920 KB |
Output is correct |
68 |
Correct |
263 ms |
57504 KB |
Output is correct |
69 |
Correct |
708 ms |
70452 KB |
Output is correct |
70 |
Correct |
551 ms |
67704 KB |
Output is correct |
71 |
Correct |
720 ms |
67964 KB |
Output is correct |
72 |
Correct |
286 ms |
52184 KB |
Output is correct |
73 |
Correct |
629 ms |
68424 KB |
Output is correct |
74 |
Correct |
305 ms |
58964 KB |
Output is correct |
75 |
Correct |
308 ms |
61064 KB |
Output is correct |
76 |
Correct |
355 ms |
60808 KB |
Output is correct |
77 |
Correct |
355 ms |
62128 KB |
Output is correct |
78 |
Correct |
327 ms |
60292 KB |
Output is correct |
79 |
Correct |
297 ms |
58780 KB |
Output is correct |
80 |
Correct |
288 ms |
62964 KB |
Output is correct |
81 |
Correct |
385 ms |
63420 KB |
Output is correct |
82 |
Correct |
298 ms |
61540 KB |
Output is correct |
83 |
Correct |
281 ms |
59340 KB |
Output is correct |
84 |
Correct |
86 ms |
38516 KB |
Output is correct |
85 |
Runtime error |
228 ms |
107772 KB |
Execution killed with signal 11 |
86 |
Halted |
0 ms |
0 KB |
- |