#include "walk.h"
#include <bits/stdc++.h>
#ifdef __LOCAL__
#include <debug_local.h>
#endif
using namespace std;
template<typename T, class F = function<T(const T&, const T&)>>
struct SparseTable {
vector<vector<T>> v;
F f;
SparseTable() { };
SparseTable(vector<T> a, F _f) : f(_f) {
int n = (int) a.size();
a.resize(n);
int lg = 32 - __builtin_clz(n);
v.resize(lg);
v[0] = a;
for (int j = 1; j < lg; j++) {
v[j].resize(n - (1 << j) + 1);
for (int i = 0; i <= n - (1 << j); i++) {
v[j][i] = f(v[j - 1][i], v[j - 1][i + (1 << (j - 1))]);
}
}
}
T query(int l, int r) {
int lg = 31 - __builtin_clz(r - l + 1);
return f(v[lg][l], v[lg][r - (1 << lg) + 1]);
}
};
const int mxN = 5e6 + 5;
vector<pair<int, int>> ad[mxN];
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();
int m = y.size();
vector<int> ys[n];
vector<int> up[n];;
SparseTable st(h, [&](auto i, auto j) { return max(i, j); });
for (int i = 0; i < m; i++) {
up[l[i]].push_back(i);
}
for (int i = 0; i < n; i++) {
ys[i].push_back(0);
ys[i].push_back(h[i]);
}
vector<tuple<int, int, int>> edges;
for (int i = 0; i < n; i++) {
for (int j : up[i]) {
ys[i].push_back(y[j]);
if (r[j] == i) continue;
int hi = r[j], lo = i + 1;
while (lo < hi) {
int mid = (lo + hi) >> 1;
if (st.query(i + 1, mid) >= y[j]) hi = mid;
else lo = mid + 1;
}
edges.push_back({i, lo, y[j]});
up[lo].push_back(j);
}
up[i].clear();
}
for (int i = 0; i < n; i++) {
sort(ys[i].begin(), ys[i].end());
ys[i].erase(unique(ys[i].begin(), ys[i].end()), ys[i].end());
}
map<pair<int, int>, int> id;
int cur = 0;
map<int, pair<int, int>> who;
for (int i = 0; i < n; i++) {
int last = 0;
for (int yy : ys[i]) {
who[cur] = {i, yy};
id[{i, yy}] = cur++;
ad[id[{i, yy}]].push_back({id[{i, last}], yy - last});
ad[id[{i, last}]].push_back({id[{i, yy}], yy - last});
last = yy;
}
}
for (auto [a, b, c] : edges) {
ad[id[{a, c}]].push_back({id[{b, c}], x[b] - x[a]});
ad[id[{b, c}]].push_back({id[{a, c}], x[b] - x[a]});
}
priority_queue<pair<long long, int>> pq;
vector<long long> dist(cur, 1e18);
dist[id[{s, 0}]] = 0;
pq.push({0, id[{s, 0}]});
while (!pq.empty()) {
auto [_, u] = pq.top();
pq.pop();
if (dist[u] != -_) continue;
for (auto [v, w] : ad[u]) {
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.push({-dist[v], v});
}
}
}
if (dist[id[{g, 0}]] != 1e18) return dist[id[{g, 0}]];
return -1;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
55 ms |
117708 KB |
Output is correct |
2 |
Correct |
53 ms |
117704 KB |
Output is correct |
3 |
Correct |
54 ms |
117644 KB |
Output is correct |
4 |
Correct |
60 ms |
117692 KB |
Output is correct |
5 |
Correct |
61 ms |
117828 KB |
Output is correct |
6 |
Correct |
54 ms |
117836 KB |
Output is correct |
7 |
Correct |
60 ms |
117828 KB |
Output is correct |
8 |
Correct |
55 ms |
117700 KB |
Output is correct |
9 |
Correct |
54 ms |
117708 KB |
Output is correct |
10 |
Correct |
55 ms |
117924 KB |
Output is correct |
11 |
Correct |
58 ms |
117668 KB |
Output is correct |
12 |
Correct |
55 ms |
117716 KB |
Output is correct |
13 |
Correct |
57 ms |
117656 KB |
Output is correct |
14 |
Correct |
55 ms |
117696 KB |
Output is correct |
15 |
Correct |
57 ms |
117716 KB |
Output is correct |
16 |
Correct |
55 ms |
117708 KB |
Output is correct |
17 |
Correct |
59 ms |
117828 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
58 ms |
117668 KB |
Output is correct |
2 |
Correct |
54 ms |
117704 KB |
Output is correct |
3 |
Correct |
1060 ms |
290800 KB |
Output is correct |
4 |
Correct |
1229 ms |
338572 KB |
Output is correct |
5 |
Correct |
965 ms |
312940 KB |
Output is correct |
6 |
Correct |
899 ms |
292984 KB |
Output is correct |
7 |
Correct |
968 ms |
313008 KB |
Output is correct |
8 |
Correct |
1335 ms |
337188 KB |
Output is correct |
9 |
Correct |
970 ms |
303952 KB |
Output is correct |
10 |
Correct |
1750 ms |
408584 KB |
Output is correct |
11 |
Correct |
610 ms |
223964 KB |
Output is correct |
12 |
Correct |
639 ms |
220656 KB |
Output is correct |
13 |
Correct |
1481 ms |
377712 KB |
Output is correct |
14 |
Correct |
468 ms |
207596 KB |
Output is correct |
15 |
Correct |
456 ms |
198772 KB |
Output is correct |
16 |
Correct |
437 ms |
198656 KB |
Output is correct |
17 |
Correct |
423 ms |
196228 KB |
Output is correct |
18 |
Correct |
930 ms |
220628 KB |
Output is correct |
19 |
Correct |
70 ms |
121452 KB |
Output is correct |
20 |
Correct |
237 ms |
156732 KB |
Output is correct |
21 |
Correct |
388 ms |
191120 KB |
Output is correct |
22 |
Correct |
453 ms |
198628 KB |
Output is correct |
23 |
Correct |
604 ms |
213356 KB |
Output is correct |
24 |
Correct |
453 ms |
197636 KB |
Output is correct |
25 |
Correct |
430 ms |
194592 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
151 ms |
137384 KB |
Output is correct |
2 |
Execution timed out |
4089 ms |
797232 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
151 ms |
137384 KB |
Output is correct |
2 |
Execution timed out |
4089 ms |
797232 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
55 ms |
117708 KB |
Output is correct |
2 |
Correct |
53 ms |
117704 KB |
Output is correct |
3 |
Correct |
54 ms |
117644 KB |
Output is correct |
4 |
Correct |
60 ms |
117692 KB |
Output is correct |
5 |
Correct |
61 ms |
117828 KB |
Output is correct |
6 |
Correct |
54 ms |
117836 KB |
Output is correct |
7 |
Correct |
60 ms |
117828 KB |
Output is correct |
8 |
Correct |
55 ms |
117700 KB |
Output is correct |
9 |
Correct |
54 ms |
117708 KB |
Output is correct |
10 |
Correct |
55 ms |
117924 KB |
Output is correct |
11 |
Correct |
58 ms |
117668 KB |
Output is correct |
12 |
Correct |
55 ms |
117716 KB |
Output is correct |
13 |
Correct |
57 ms |
117656 KB |
Output is correct |
14 |
Correct |
55 ms |
117696 KB |
Output is correct |
15 |
Correct |
57 ms |
117716 KB |
Output is correct |
16 |
Correct |
55 ms |
117708 KB |
Output is correct |
17 |
Correct |
59 ms |
117828 KB |
Output is correct |
18 |
Correct |
58 ms |
117668 KB |
Output is correct |
19 |
Correct |
54 ms |
117704 KB |
Output is correct |
20 |
Correct |
1060 ms |
290800 KB |
Output is correct |
21 |
Correct |
1229 ms |
338572 KB |
Output is correct |
22 |
Correct |
965 ms |
312940 KB |
Output is correct |
23 |
Correct |
899 ms |
292984 KB |
Output is correct |
24 |
Correct |
968 ms |
313008 KB |
Output is correct |
25 |
Correct |
1335 ms |
337188 KB |
Output is correct |
26 |
Correct |
970 ms |
303952 KB |
Output is correct |
27 |
Correct |
1750 ms |
408584 KB |
Output is correct |
28 |
Correct |
610 ms |
223964 KB |
Output is correct |
29 |
Correct |
639 ms |
220656 KB |
Output is correct |
30 |
Correct |
1481 ms |
377712 KB |
Output is correct |
31 |
Correct |
468 ms |
207596 KB |
Output is correct |
32 |
Correct |
456 ms |
198772 KB |
Output is correct |
33 |
Correct |
437 ms |
198656 KB |
Output is correct |
34 |
Correct |
423 ms |
196228 KB |
Output is correct |
35 |
Correct |
930 ms |
220628 KB |
Output is correct |
36 |
Correct |
70 ms |
121452 KB |
Output is correct |
37 |
Correct |
237 ms |
156732 KB |
Output is correct |
38 |
Correct |
388 ms |
191120 KB |
Output is correct |
39 |
Correct |
453 ms |
198628 KB |
Output is correct |
40 |
Correct |
604 ms |
213356 KB |
Output is correct |
41 |
Correct |
453 ms |
197636 KB |
Output is correct |
42 |
Correct |
430 ms |
194592 KB |
Output is correct |
43 |
Correct |
151 ms |
137384 KB |
Output is correct |
44 |
Execution timed out |
4089 ms |
797232 KB |
Time limit exceeded |
45 |
Halted |
0 ms |
0 KB |
- |