#include <bits/stdc++.h>
using namespace std;
struct segtree {
segtree *left, *right;
int value;
segtree(int l, int r) {
if (l == r) {
value = 0;
} else {
value = -1;
int m = (l + r) / 2;
left = new segtree(l, m);
right = new segtree(m + 1, r);
}
}
void push() {
if (value != -1) {
left->value = right->value = value;
value = -1;
}
}
void update(int x, int a, int b, int l, int r) {
if (b < l || r < a) {
return;
} else if (a <= l && r <= b) {
value = x;
} else {
push();
int m = (l + r) / 2;
left->update(x, a, b, l, m);
right->update(x, a, b, m + 1, r);
}
}
int query(int a, int l, int r) {
if (l == r) {
return value;
} else {
push();
int m = (l + r) / 2;
if (a <= m) {
return left->query(a, l, m);
} else {
return right->query(a, m + 1, r);
}
}
}
};
long long 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();
vector<array<int, 3>> events;
for (int i = 0; i < n; ++i) {
events.push_back({h[i], INT_MAX, i});
}
for (int i = 0; i < m; ++i) {
events.push_back({y[i], l[i], r[i]});
}
sort(events.begin(), events.end());
set<int> buildings;
for (int i = 0; i < n; ++i) {
buildings.insert(i);
}
vector<map<int, vector<array<int, 2>>>> adj(n);
segtree *prv = new segtree(0, n - 1);
vector<array<int, 3>> skywalks;
map<int, set<int>> nodes;
for (auto [i, a, b] : events) {
if (a == INT_MAX) {
buildings.erase(b);
} else {
set<int> segments = {a, b};
for (auto j : {s, g}) {
auto it = buildings.lower_bound(j);
if (it != buildings.end()) {
segments.insert(*it);
}
it = buildings.upper_bound(j);
if (it != buildings.begin()) {
segments.insert(*--it);
}
}
while (*segments.begin() < a) {
segments.erase(segments.begin());
}
while (*--segments.end() > b) {
segments.erase(--segments.end());
}
for (auto j : segments) {
int k = prv->query(j, 0, n - 1);
adj[j][k].push_back({j, i});
adj[j][i].push_back({j, k});
nodes[k].insert(j);
nodes[i].insert(j);
}
prv->update(i, a, b, 0, n - 1);
}
}
for (int i = 0; i < m; ++i) {
auto it = nodes[y[i]].lower_bound(l[i]);
while (*it != r[i]) {
auto nxt = it; ++nxt;
adj[*nxt][y[i]].push_back({*it, y[i]});
adj[*it][y[i]].push_back({*nxt, y[i]});
it = nxt;
}
}
priority_queue<tuple<long long, int, int>> dijkstra;
vector<map<int, long long>> dist(n);
dijkstra.push({0, s, 0});
dist[s][0] = 0;
while (!dijkstra.empty()) {
auto [d, i, j] = dijkstra.top();
dijkstra.pop();
d = -d;
if (d > dist[i][j]) {
continue;
}
if (i == g && j == 0) {
return d;
}
for (auto [ic, jc] : adj[i][j]) {
int w = i == ic ? abs(j - jc) : abs(x[i] - x[ic]);
if (dist[ic].count(jc) == 0 || d + w < dist[ic][jc]) {
dijkstra.push({-(d + w), ic, jc});
dist[ic][jc] = d + w;
}
}
}
return -1;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
2 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
2 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
969 ms |
78632 KB |
Output is correct |
4 |
Correct |
1304 ms |
120996 KB |
Output is correct |
5 |
Correct |
732 ms |
80356 KB |
Output is correct |
6 |
Correct |
766 ms |
79544 KB |
Output is correct |
7 |
Correct |
768 ms |
81024 KB |
Output is correct |
8 |
Correct |
1075 ms |
84552 KB |
Output is correct |
9 |
Correct |
1077 ms |
96692 KB |
Output is correct |
10 |
Correct |
1273 ms |
119784 KB |
Output is correct |
11 |
Correct |
956 ms |
82820 KB |
Output is correct |
12 |
Correct |
1046 ms |
105712 KB |
Output is correct |
13 |
Correct |
1256 ms |
125744 KB |
Output is correct |
14 |
Correct |
705 ms |
81404 KB |
Output is correct |
15 |
Correct |
781 ms |
98384 KB |
Output is correct |
16 |
Correct |
737 ms |
92824 KB |
Output is correct |
17 |
Correct |
780 ms |
88560 KB |
Output is correct |
18 |
Correct |
875 ms |
88984 KB |
Output is correct |
19 |
Correct |
20 ms |
5240 KB |
Output is correct |
20 |
Correct |
263 ms |
50996 KB |
Output is correct |
21 |
Correct |
653 ms |
86100 KB |
Output is correct |
22 |
Correct |
598 ms |
77064 KB |
Output is correct |
23 |
Correct |
856 ms |
103376 KB |
Output is correct |
24 |
Correct |
686 ms |
91872 KB |
Output is correct |
25 |
Correct |
742 ms |
87956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
208 ms |
22620 KB |
Output is correct |
2 |
Correct |
1606 ms |
98868 KB |
Output is correct |
3 |
Correct |
1599 ms |
112552 KB |
Output is correct |
4 |
Correct |
1408 ms |
128112 KB |
Output is correct |
5 |
Correct |
1322 ms |
124444 KB |
Output is correct |
6 |
Correct |
1297 ms |
121508 KB |
Output is correct |
7 |
Correct |
647 ms |
77588 KB |
Output is correct |
8 |
Correct |
993 ms |
106068 KB |
Output is correct |
9 |
Correct |
1220 ms |
115764 KB |
Output is correct |
10 |
Correct |
772 ms |
83064 KB |
Output is correct |
11 |
Correct |
46 ms |
12604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
208 ms |
22620 KB |
Output is correct |
2 |
Correct |
1606 ms |
98868 KB |
Output is correct |
3 |
Correct |
1599 ms |
112552 KB |
Output is correct |
4 |
Correct |
1408 ms |
128112 KB |
Output is correct |
5 |
Correct |
1322 ms |
124444 KB |
Output is correct |
6 |
Correct |
1297 ms |
121508 KB |
Output is correct |
7 |
Correct |
647 ms |
77588 KB |
Output is correct |
8 |
Correct |
993 ms |
106068 KB |
Output is correct |
9 |
Correct |
1220 ms |
115764 KB |
Output is correct |
10 |
Correct |
772 ms |
83064 KB |
Output is correct |
11 |
Correct |
46 ms |
12604 KB |
Output is correct |
12 |
Correct |
1601 ms |
109784 KB |
Output is correct |
13 |
Correct |
1149 ms |
107432 KB |
Output is correct |
14 |
Correct |
1476 ms |
125808 KB |
Output is correct |
15 |
Correct |
1040 ms |
112032 KB |
Output is correct |
16 |
Correct |
1027 ms |
108472 KB |
Output is correct |
17 |
Correct |
1195 ms |
125748 KB |
Output is correct |
18 |
Correct |
1078 ms |
112084 KB |
Output is correct |
19 |
Correct |
1114 ms |
111432 KB |
Output is correct |
20 |
Correct |
725 ms |
73688 KB |
Output is correct |
21 |
Correct |
153 ms |
25492 KB |
Output is correct |
22 |
Correct |
860 ms |
89848 KB |
Output is correct |
23 |
Correct |
848 ms |
89144 KB |
Output is correct |
24 |
Correct |
778 ms |
82028 KB |
Output is correct |
25 |
Correct |
861 ms |
86308 KB |
Output is correct |
26 |
Correct |
810 ms |
81488 KB |
Output is correct |
27 |
Correct |
1360 ms |
124852 KB |
Output is correct |
28 |
Correct |
1117 ms |
107008 KB |
Output is correct |
29 |
Correct |
1462 ms |
123716 KB |
Output is correct |
30 |
Correct |
704 ms |
76880 KB |
Output is correct |
31 |
Correct |
1186 ms |
114872 KB |
Output is correct |
32 |
Correct |
748 ms |
89504 KB |
Output is correct |
33 |
Correct |
689 ms |
80192 KB |
Output is correct |
34 |
Correct |
799 ms |
92356 KB |
Output is correct |
35 |
Correct |
821 ms |
99336 KB |
Output is correct |
36 |
Correct |
799 ms |
93612 KB |
Output is correct |
37 |
Correct |
681 ms |
86148 KB |
Output is correct |
38 |
Correct |
605 ms |
77156 KB |
Output is correct |
39 |
Correct |
859 ms |
103368 KB |
Output is correct |
40 |
Correct |
726 ms |
91884 KB |
Output is correct |
41 |
Correct |
690 ms |
87992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
2 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
2 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
300 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
969 ms |
78632 KB |
Output is correct |
21 |
Correct |
1304 ms |
120996 KB |
Output is correct |
22 |
Correct |
732 ms |
80356 KB |
Output is correct |
23 |
Correct |
766 ms |
79544 KB |
Output is correct |
24 |
Correct |
768 ms |
81024 KB |
Output is correct |
25 |
Correct |
1075 ms |
84552 KB |
Output is correct |
26 |
Correct |
1077 ms |
96692 KB |
Output is correct |
27 |
Correct |
1273 ms |
119784 KB |
Output is correct |
28 |
Correct |
956 ms |
82820 KB |
Output is correct |
29 |
Correct |
1046 ms |
105712 KB |
Output is correct |
30 |
Correct |
1256 ms |
125744 KB |
Output is correct |
31 |
Correct |
705 ms |
81404 KB |
Output is correct |
32 |
Correct |
781 ms |
98384 KB |
Output is correct |
33 |
Correct |
737 ms |
92824 KB |
Output is correct |
34 |
Correct |
780 ms |
88560 KB |
Output is correct |
35 |
Correct |
875 ms |
88984 KB |
Output is correct |
36 |
Correct |
20 ms |
5240 KB |
Output is correct |
37 |
Correct |
263 ms |
50996 KB |
Output is correct |
38 |
Correct |
653 ms |
86100 KB |
Output is correct |
39 |
Correct |
598 ms |
77064 KB |
Output is correct |
40 |
Correct |
856 ms |
103376 KB |
Output is correct |
41 |
Correct |
686 ms |
91872 KB |
Output is correct |
42 |
Correct |
742 ms |
87956 KB |
Output is correct |
43 |
Correct |
208 ms |
22620 KB |
Output is correct |
44 |
Correct |
1606 ms |
98868 KB |
Output is correct |
45 |
Correct |
1599 ms |
112552 KB |
Output is correct |
46 |
Correct |
1408 ms |
128112 KB |
Output is correct |
47 |
Correct |
1322 ms |
124444 KB |
Output is correct |
48 |
Correct |
1297 ms |
121508 KB |
Output is correct |
49 |
Correct |
647 ms |
77588 KB |
Output is correct |
50 |
Correct |
993 ms |
106068 KB |
Output is correct |
51 |
Correct |
1220 ms |
115764 KB |
Output is correct |
52 |
Correct |
772 ms |
83064 KB |
Output is correct |
53 |
Correct |
46 ms |
12604 KB |
Output is correct |
54 |
Correct |
1601 ms |
109784 KB |
Output is correct |
55 |
Correct |
1149 ms |
107432 KB |
Output is correct |
56 |
Correct |
1476 ms |
125808 KB |
Output is correct |
57 |
Correct |
1040 ms |
112032 KB |
Output is correct |
58 |
Correct |
1027 ms |
108472 KB |
Output is correct |
59 |
Correct |
1195 ms |
125748 KB |
Output is correct |
60 |
Correct |
1078 ms |
112084 KB |
Output is correct |
61 |
Correct |
1114 ms |
111432 KB |
Output is correct |
62 |
Correct |
725 ms |
73688 KB |
Output is correct |
63 |
Correct |
153 ms |
25492 KB |
Output is correct |
64 |
Correct |
860 ms |
89848 KB |
Output is correct |
65 |
Correct |
848 ms |
89144 KB |
Output is correct |
66 |
Correct |
778 ms |
82028 KB |
Output is correct |
67 |
Correct |
861 ms |
86308 KB |
Output is correct |
68 |
Correct |
810 ms |
81488 KB |
Output is correct |
69 |
Correct |
1360 ms |
124852 KB |
Output is correct |
70 |
Correct |
1117 ms |
107008 KB |
Output is correct |
71 |
Correct |
1462 ms |
123716 KB |
Output is correct |
72 |
Correct |
704 ms |
76880 KB |
Output is correct |
73 |
Correct |
1186 ms |
114872 KB |
Output is correct |
74 |
Correct |
748 ms |
89504 KB |
Output is correct |
75 |
Correct |
689 ms |
80192 KB |
Output is correct |
76 |
Correct |
799 ms |
92356 KB |
Output is correct |
77 |
Correct |
821 ms |
99336 KB |
Output is correct |
78 |
Correct |
799 ms |
93612 KB |
Output is correct |
79 |
Correct |
681 ms |
86148 KB |
Output is correct |
80 |
Correct |
605 ms |
77156 KB |
Output is correct |
81 |
Correct |
859 ms |
103368 KB |
Output is correct |
82 |
Correct |
726 ms |
91884 KB |
Output is correct |
83 |
Correct |
690 ms |
87992 KB |
Output is correct |
84 |
Correct |
157 ms |
18656 KB |
Output is correct |
85 |
Correct |
1405 ms |
104100 KB |
Output is correct |
86 |
Correct |
1740 ms |
144940 KB |
Output is correct |
87 |
Correct |
140 ms |
32276 KB |
Output is correct |
88 |
Correct |
169 ms |
30744 KB |
Output is correct |
89 |
Correct |
141 ms |
32188 KB |
Output is correct |
90 |
Correct |
44 ms |
7836 KB |
Output is correct |
91 |
Correct |
2 ms |
588 KB |
Output is correct |
92 |
Correct |
30 ms |
5656 KB |
Output is correct |
93 |
Correct |
443 ms |
51016 KB |
Output is correct |
94 |
Correct |
128 ms |
25640 KB |
Output is correct |
95 |
Correct |
843 ms |
93584 KB |
Output is correct |
96 |
Correct |
824 ms |
89804 KB |
Output is correct |
97 |
Correct |
755 ms |
81872 KB |
Output is correct |
98 |
Correct |
799 ms |
86340 KB |
Output is correct |
99 |
Correct |
1833 ms |
160332 KB |
Output is correct |
100 |
Correct |
1321 ms |
122288 KB |
Output is correct |
101 |
Correct |
1283 ms |
120088 KB |
Output is correct |
102 |
Correct |
580 ms |
67204 KB |
Output is correct |
103 |
Correct |
728 ms |
89212 KB |
Output is correct |
104 |
Correct |
659 ms |
80052 KB |
Output is correct |
105 |
Correct |
797 ms |
92460 KB |
Output is correct |
106 |
Correct |
746 ms |
96580 KB |
Output is correct |
107 |
Correct |
783 ms |
101876 KB |
Output is correct |
108 |
Correct |
64 ms |
10908 KB |
Output is correct |
109 |
Correct |
1164 ms |
108108 KB |
Output is correct |
110 |
Correct |
1081 ms |
112768 KB |
Output is correct |
111 |
Correct |
1107 ms |
107968 KB |
Output is correct |
112 |
Correct |
798 ms |
96824 KB |
Output is correct |
113 |
Correct |
802 ms |
95444 KB |
Output is correct |