#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;
using int64 = long long;
using ld = long double;
constexpr int kInf = 1e9 + 10;
constexpr int64 kInf64 = 1e17 + 10;
constexpr int kMod = 1e9 + 7;
class LazySegTree {
const int n;
vector<int> t;
void push(const int x, const int l, const int r) {
if (t[x] == -1) return;
const int mid = (l + r) / 2;
const int y = 2 * (mid - l + 1) + x;
for (const int child : {x + 1, y}) {
t[child] = t[x];
}
t[x] = -1;
}
void update(const int x, const int l, const int r, const int ql, const int qr, const int i) {
if (ql <= l and r <= qr) {
t[x] = i;
return;
}
push(x, l, r);
const int mid = (l + r) / 2;
const int y = 2 * (mid - l + 1) + x;
if (ql <= mid) {
update(x + 1, l, mid, ql, qr, i);
}
if (mid < qr) {
update(y, mid + 1, r, ql, qr, i);
}
}
int query(const int x, const int l, const int r, const int p) {
if (l == r) {
return t[x];
}
push(x, l, r);
const int mid = (l + r) / 2;
const int y = 2 * (mid - l + 1) + x;
if (p <= mid) {
return query(x + 1, l, mid, p);
} else {
return query(y, mid + 1, r, p);
}
}
public:
explicit LazySegTree(const int n) : n(n), t(2 * n - 1, -1) {}
void update(const int l, const int r, const int i) {
update(0, 0, n - 1, l, r, i);
}
int query(const int p) {
return query(0, 0, n - 1, p);
}
};
pair<vector<int64>, vector<int>> dijkstra(const vector<vector<pair<int, int>>> &g, const int s) {
const int n = (int) g.size();
vector<int64> d(n, kInf64);
vector<int> p(n, -1);
min_heap<pair<int64, int>> q;
d[s] = 0;
q.push({0, s});
while (not q.empty()) {
const auto [dist, x] = q.top();
q.pop();
if (d[x] < dist) continue;
for (const auto &[y, w] : g[x]) {
if (d[y] <= d[x] + w) continue;
d[y] = d[x] + w;
p[y] = x;
q.push({d[y], y});
}
}
return make_pair(d, p);
}
struct building {
int x;
int h;
};
struct skywalk {
int l;
int r;
int h;
set<pair<int, int>> nodes;
skywalk() = default;
skywalk(const int l, const int r, const int h) : l(l), r(r), h(h) {}
bool operator<(const skywalk &other) const {
if (h != other.h) return h < other.h;
if (l != other.l) return l < other.l;
return r < other.r;
}
void add_node(const int node, const int x) {
nodes.insert({x, node});
}
pair<int, int> get_prev(const int x) const {
return *prev(nodes.upper_bound({x, kInf}));
}
pair<int, int> get_next(const int x) const {
return *nodes.upper_bound({x, -1});
}
};
int64 subtask4(const vector<building> &buildings, vector<skywalk> &skywalks, int S, int G) {
const int n = buildings.size();
sort(skywalks.begin(), skywalks.end());
vector<vector<pair<int, int>>> g(n);
LazySegTree st(n);
auto add_node = [&]() -> int {
g.emplace_back();
return g.size() - 1;
};
auto add_edge = [&](const int x, const int y, const int w) -> void {
g[x].emplace_back(y, w);
g[y].emplace_back(x, w);
};
auto add_vert = [&](const int i, const int h, const int u) {
const int x = buildings[i].x;
const int s = st.query(i);
if (s == -1) {
add_edge(u, i, h);
return;
}
const int v = add_node();
auto before = skywalks[s].get_prev(x);
add_edge(before.second, v, x - before.first);
auto after = skywalks[s].get_next(x);
add_edge(after.second, v, after.first - x);
add_edge(u, v, h - skywalks[s].h);
skywalks[s].add_node(v, x);
};
for (int i = 0; i < skywalks.size(); i++) {
skywalk &s = skywalks[i];
const int l = s.l;
const int r = s.r;
const int h = s.h;
const int x = add_node();
const int y = add_node();
add_edge(x, y, buildings[r].x - buildings[l].x);
add_vert(l, h, x);
add_vert(r, h, y);
s.add_node(x, buildings[l].x);
s.add_node(y, buildings[r].x);
st.update(l, r, i);
}
const int64 ans = dijkstra(g, S).first[G];
return (ans == kInf64 ? -1 : ans);
}
int64 min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int S, int G) {
const int n = X.size();
int m = L.size();
vector<building> buildings(n);
for (int i = 0; i < n; i++) {
buildings[i].h = H[i];
buildings[i].x = X[i];
}
vector<skywalk> skywalks(m);
for (int j = 0; j < m; j++) {
skywalks[j].l = L[j];
skywalks[j].r = R[j];
skywalks[j].h = Y[j];
}
auto add_skywalks = [&](const int x) {
vector<pair<int, int>> A = {{kInf, -1}};
for (int i = 0; i <= x; i++) {
while (A.back().first < H[i]) {
A.pop_back();
}
A.emplace_back(H[i], i);
}
vector<pair<int, int>> B = {{kInf, -1}};
for (int i = n - 1; i >= x; i--) {
while (B.back().first < H[i]) {
B.pop_back();
}
B.emplace_back(H[i], i);
}
vector<skywalk> temp;
swap(temp, skywalks);
for (const skywalk &s : temp) {
if (not(s.l < x and x < s.r)) {
skywalks.push_back(s);
continue;
}
const int a = lower_bound(A.rbegin(), A.rend(), make_pair(s.h, -1))->second;
const int b = lower_bound(B.rbegin(), B.rend(), make_pair(s.h, -1))->second;
skywalks.emplace_back(s.l, a, s.h);
skywalks.emplace_back(a, b, s.h);
skywalks.emplace_back(b, s.r, s.h);
}
};
add_skywalks(S);
add_skywalks(G);
return subtask4(buildings, skywalks, S, G);
}
Compilation message
walk.cpp: In function 'int64 subtask4(const std::vector<building>&, std::vector<skywalk>&, int, int)':
walk.cpp:172:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<skywalk>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
172 | for (int i = 0; i < skywalks.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
304 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
304 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
300 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
296 KB |
Output is correct |
17 |
Correct |
1 ms |
300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
374 ms |
69292 KB |
Output is correct |
4 |
Correct |
441 ms |
73600 KB |
Output is correct |
5 |
Correct |
261 ms |
58148 KB |
Output is correct |
6 |
Correct |
333 ms |
81996 KB |
Output is correct |
7 |
Correct |
252 ms |
57824 KB |
Output is correct |
8 |
Correct |
388 ms |
69412 KB |
Output is correct |
9 |
Correct |
355 ms |
71488 KB |
Output is correct |
10 |
Correct |
462 ms |
74276 KB |
Output is correct |
11 |
Correct |
442 ms |
68972 KB |
Output is correct |
12 |
Correct |
384 ms |
62896 KB |
Output is correct |
13 |
Correct |
476 ms |
74300 KB |
Output is correct |
14 |
Correct |
670 ms |
180888 KB |
Output is correct |
15 |
Correct |
501 ms |
127704 KB |
Output is correct |
16 |
Correct |
275 ms |
71916 KB |
Output is correct |
17 |
Correct |
257 ms |
65376 KB |
Output is correct |
18 |
Correct |
251 ms |
76988 KB |
Output is correct |
19 |
Correct |
30 ms |
9160 KB |
Output is correct |
20 |
Correct |
324 ms |
89824 KB |
Output is correct |
21 |
Correct |
245 ms |
64008 KB |
Output is correct |
22 |
Correct |
222 ms |
62792 KB |
Output is correct |
23 |
Correct |
263 ms |
70792 KB |
Output is correct |
24 |
Correct |
256 ms |
64276 KB |
Output is correct |
25 |
Correct |
233 ms |
64728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
104 ms |
32652 KB |
Output is correct |
2 |
Correct |
397 ms |
68552 KB |
Output is correct |
3 |
Correct |
368 ms |
69344 KB |
Output is correct |
4 |
Correct |
456 ms |
76368 KB |
Output is correct |
5 |
Correct |
402 ms |
77632 KB |
Output is correct |
6 |
Correct |
416 ms |
77360 KB |
Output is correct |
7 |
Correct |
209 ms |
43468 KB |
Output is correct |
8 |
Correct |
361 ms |
62580 KB |
Output is correct |
9 |
Correct |
402 ms |
77972 KB |
Output is correct |
10 |
Correct |
221 ms |
69688 KB |
Output is correct |
11 |
Correct |
12 ms |
5016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
104 ms |
32652 KB |
Output is correct |
2 |
Correct |
397 ms |
68552 KB |
Output is correct |
3 |
Correct |
368 ms |
69344 KB |
Output is correct |
4 |
Correct |
456 ms |
76368 KB |
Output is correct |
5 |
Correct |
402 ms |
77632 KB |
Output is correct |
6 |
Correct |
416 ms |
77360 KB |
Output is correct |
7 |
Correct |
209 ms |
43468 KB |
Output is correct |
8 |
Correct |
361 ms |
62580 KB |
Output is correct |
9 |
Correct |
402 ms |
77972 KB |
Output is correct |
10 |
Correct |
221 ms |
69688 KB |
Output is correct |
11 |
Correct |
12 ms |
5016 KB |
Output is correct |
12 |
Correct |
382 ms |
69356 KB |
Output is correct |
13 |
Correct |
283 ms |
76116 KB |
Output is correct |
14 |
Correct |
404 ms |
77524 KB |
Output is correct |
15 |
Correct |
290 ms |
67388 KB |
Output is correct |
16 |
Correct |
310 ms |
75608 KB |
Output is correct |
17 |
Correct |
380 ms |
75376 KB |
Output is correct |
18 |
Correct |
284 ms |
67360 KB |
Output is correct |
19 |
Correct |
331 ms |
75820 KB |
Output is correct |
20 |
Correct |
203 ms |
43360 KB |
Output is correct |
21 |
Correct |
27 ms |
10688 KB |
Output is correct |
22 |
Correct |
254 ms |
65116 KB |
Output is correct |
23 |
Correct |
264 ms |
67212 KB |
Output is correct |
24 |
Correct |
264 ms |
63344 KB |
Output is correct |
25 |
Correct |
285 ms |
63288 KB |
Output is correct |
26 |
Correct |
231 ms |
57116 KB |
Output is correct |
27 |
Correct |
384 ms |
77012 KB |
Output is correct |
28 |
Correct |
289 ms |
75728 KB |
Output is correct |
29 |
Correct |
393 ms |
77000 KB |
Output is correct |
30 |
Correct |
210 ms |
43304 KB |
Output is correct |
31 |
Correct |
372 ms |
77956 KB |
Output is correct |
32 |
Correct |
221 ms |
66360 KB |
Output is correct |
33 |
Correct |
210 ms |
65780 KB |
Output is correct |
34 |
Correct |
236 ms |
69328 KB |
Output is correct |
35 |
Correct |
248 ms |
67160 KB |
Output is correct |
36 |
Correct |
262 ms |
64648 KB |
Output is correct |
37 |
Correct |
211 ms |
63320 KB |
Output is correct |
38 |
Correct |
202 ms |
62180 KB |
Output is correct |
39 |
Correct |
257 ms |
70340 KB |
Output is correct |
40 |
Correct |
212 ms |
63352 KB |
Output is correct |
41 |
Correct |
243 ms |
64172 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
304 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
304 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
300 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
296 KB |
Output is correct |
17 |
Correct |
1 ms |
300 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
374 ms |
69292 KB |
Output is correct |
21 |
Correct |
441 ms |
73600 KB |
Output is correct |
22 |
Correct |
261 ms |
58148 KB |
Output is correct |
23 |
Correct |
333 ms |
81996 KB |
Output is correct |
24 |
Correct |
252 ms |
57824 KB |
Output is correct |
25 |
Correct |
388 ms |
69412 KB |
Output is correct |
26 |
Correct |
355 ms |
71488 KB |
Output is correct |
27 |
Correct |
462 ms |
74276 KB |
Output is correct |
28 |
Correct |
442 ms |
68972 KB |
Output is correct |
29 |
Correct |
384 ms |
62896 KB |
Output is correct |
30 |
Correct |
476 ms |
74300 KB |
Output is correct |
31 |
Correct |
670 ms |
180888 KB |
Output is correct |
32 |
Correct |
501 ms |
127704 KB |
Output is correct |
33 |
Correct |
275 ms |
71916 KB |
Output is correct |
34 |
Correct |
257 ms |
65376 KB |
Output is correct |
35 |
Correct |
251 ms |
76988 KB |
Output is correct |
36 |
Correct |
30 ms |
9160 KB |
Output is correct |
37 |
Correct |
324 ms |
89824 KB |
Output is correct |
38 |
Correct |
245 ms |
64008 KB |
Output is correct |
39 |
Correct |
222 ms |
62792 KB |
Output is correct |
40 |
Correct |
263 ms |
70792 KB |
Output is correct |
41 |
Correct |
256 ms |
64276 KB |
Output is correct |
42 |
Correct |
233 ms |
64728 KB |
Output is correct |
43 |
Correct |
104 ms |
32652 KB |
Output is correct |
44 |
Correct |
397 ms |
68552 KB |
Output is correct |
45 |
Correct |
368 ms |
69344 KB |
Output is correct |
46 |
Correct |
456 ms |
76368 KB |
Output is correct |
47 |
Correct |
402 ms |
77632 KB |
Output is correct |
48 |
Correct |
416 ms |
77360 KB |
Output is correct |
49 |
Correct |
209 ms |
43468 KB |
Output is correct |
50 |
Correct |
361 ms |
62580 KB |
Output is correct |
51 |
Correct |
402 ms |
77972 KB |
Output is correct |
52 |
Correct |
221 ms |
69688 KB |
Output is correct |
53 |
Correct |
12 ms |
5016 KB |
Output is correct |
54 |
Correct |
382 ms |
69356 KB |
Output is correct |
55 |
Correct |
283 ms |
76116 KB |
Output is correct |
56 |
Correct |
404 ms |
77524 KB |
Output is correct |
57 |
Correct |
290 ms |
67388 KB |
Output is correct |
58 |
Correct |
310 ms |
75608 KB |
Output is correct |
59 |
Correct |
380 ms |
75376 KB |
Output is correct |
60 |
Correct |
284 ms |
67360 KB |
Output is correct |
61 |
Correct |
331 ms |
75820 KB |
Output is correct |
62 |
Correct |
203 ms |
43360 KB |
Output is correct |
63 |
Correct |
27 ms |
10688 KB |
Output is correct |
64 |
Correct |
254 ms |
65116 KB |
Output is correct |
65 |
Correct |
264 ms |
67212 KB |
Output is correct |
66 |
Correct |
264 ms |
63344 KB |
Output is correct |
67 |
Correct |
285 ms |
63288 KB |
Output is correct |
68 |
Correct |
231 ms |
57116 KB |
Output is correct |
69 |
Correct |
384 ms |
77012 KB |
Output is correct |
70 |
Correct |
289 ms |
75728 KB |
Output is correct |
71 |
Correct |
393 ms |
77000 KB |
Output is correct |
72 |
Correct |
210 ms |
43304 KB |
Output is correct |
73 |
Correct |
372 ms |
77956 KB |
Output is correct |
74 |
Correct |
221 ms |
66360 KB |
Output is correct |
75 |
Correct |
210 ms |
65780 KB |
Output is correct |
76 |
Correct |
236 ms |
69328 KB |
Output is correct |
77 |
Correct |
248 ms |
67160 KB |
Output is correct |
78 |
Correct |
262 ms |
64648 KB |
Output is correct |
79 |
Correct |
211 ms |
63320 KB |
Output is correct |
80 |
Correct |
202 ms |
62180 KB |
Output is correct |
81 |
Correct |
257 ms |
70340 KB |
Output is correct |
82 |
Correct |
212 ms |
63352 KB |
Output is correct |
83 |
Correct |
243 ms |
64172 KB |
Output is correct |
84 |
Correct |
85 ms |
25420 KB |
Output is correct |
85 |
Correct |
433 ms |
82516 KB |
Output is correct |
86 |
Correct |
803 ms |
175028 KB |
Output is correct |
87 |
Correct |
52 ms |
15516 KB |
Output is correct |
88 |
Correct |
54 ms |
16796 KB |
Output is correct |
89 |
Correct |
47 ms |
15516 KB |
Output is correct |
90 |
Correct |
21 ms |
7592 KB |
Output is correct |
91 |
Correct |
1 ms |
596 KB |
Output is correct |
92 |
Correct |
13 ms |
4012 KB |
Output is correct |
93 |
Correct |
163 ms |
36324 KB |
Output is correct |
94 |
Correct |
34 ms |
11732 KB |
Output is correct |
95 |
Correct |
279 ms |
67676 KB |
Output is correct |
96 |
Correct |
277 ms |
72112 KB |
Output is correct |
97 |
Correct |
441 ms |
112188 KB |
Output is correct |
98 |
Correct |
279 ms |
62848 KB |
Output is correct |
99 |
Correct |
1244 ms |
266320 KB |
Output is correct |
100 |
Correct |
415 ms |
76832 KB |
Output is correct |
101 |
Correct |
756 ms |
156392 KB |
Output is correct |
102 |
Correct |
220 ms |
43940 KB |
Output is correct |
103 |
Correct |
233 ms |
65820 KB |
Output is correct |
104 |
Correct |
226 ms |
65172 KB |
Output is correct |
105 |
Correct |
261 ms |
68680 KB |
Output is correct |
106 |
Correct |
351 ms |
97780 KB |
Output is correct |
107 |
Correct |
350 ms |
97992 KB |
Output is correct |
108 |
Correct |
27 ms |
7832 KB |
Output is correct |
109 |
Correct |
359 ms |
72612 KB |
Output is correct |
110 |
Correct |
317 ms |
77264 KB |
Output is correct |
111 |
Correct |
304 ms |
80064 KB |
Output is correct |
112 |
Correct |
289 ms |
73596 KB |
Output is correct |
113 |
Correct |
281 ms |
67820 KB |
Output is correct |