#include "walk.h"
#include <bits/stdc++.h>
#ifdef __LOCAL__
#include <debug_local.h>
#endif
using namespace std;
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();
multiset<pair<int, long long>> st;
vector<int> add[n], rem[n];
for (int i = 0; i < m; i++) {
add[l[i]].push_back(i);
rem[r[i]].push_back(i);
}
vector<long long> ans(m);
for (int i = 0; i < n; i++) {
vector<pair<int, long long>> nw;
for (int j : add[i]) {
if (i == 0) nw.push_back({y[j], y[j]}), ans[j] = y[j];
else {
long long v = 1e18;
auto up = st.upper_bound({y[j], -5});
if (up != st.end()) v = min(v, (*up).first - y[j] + (*up).second);
auto down = st.lower_bound({y[j], -5});
if (!st.empty() && up == down && down != st.begin()) {
down--;
v = min(v, y[j] - (*down).first + (*down).second);
}
ans[j] = v;
nw.push_back({y[j], ans[j]});
}
}
for (auto x : nw) st.insert(x);
for (int j : rem[i]) if (st.find({y[j], ans[j]}) != st.end()) st.erase(st.find({y[j], ans[j]}));
}
long long ret = 1e18;
for (int i = 0; i < m; i++) {
if (r[i] == n - 1) ret = min(ret, ans[i] + y[i] + x[n - 1] - x[0]);
}
if (ret == 1e18) ret = -1;
return ret;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
3396 KB |
Output is correct |
2 |
Correct |
101 ms |
4912 KB |
Output is correct |
3 |
Correct |
108 ms |
5912 KB |
Output is correct |
4 |
Correct |
133 ms |
13884 KB |
Output is correct |
5 |
Correct |
215 ms |
18368 KB |
Output is correct |
6 |
Correct |
165 ms |
16276 KB |
Output is correct |
7 |
Correct |
69 ms |
11140 KB |
Output is correct |
8 |
Correct |
94 ms |
15824 KB |
Output is correct |
9 |
Correct |
189 ms |
21792 KB |
Output is correct |
10 |
Correct |
108 ms |
20120 KB |
Output is correct |
11 |
Correct |
12 ms |
4140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
3396 KB |
Output is correct |
2 |
Correct |
101 ms |
4912 KB |
Output is correct |
3 |
Correct |
108 ms |
5912 KB |
Output is correct |
4 |
Correct |
133 ms |
13884 KB |
Output is correct |
5 |
Correct |
215 ms |
18368 KB |
Output is correct |
6 |
Correct |
165 ms |
16276 KB |
Output is correct |
7 |
Correct |
69 ms |
11140 KB |
Output is correct |
8 |
Correct |
94 ms |
15824 KB |
Output is correct |
9 |
Correct |
189 ms |
21792 KB |
Output is correct |
10 |
Correct |
108 ms |
20120 KB |
Output is correct |
11 |
Correct |
12 ms |
4140 KB |
Output is correct |
12 |
Correct |
106 ms |
8036 KB |
Output is correct |
13 |
Correct |
146 ms |
17960 KB |
Output is correct |
14 |
Correct |
193 ms |
22344 KB |
Output is correct |
15 |
Correct |
119 ms |
17708 KB |
Output is correct |
16 |
Correct |
111 ms |
17988 KB |
Output is correct |
17 |
Correct |
120 ms |
18012 KB |
Output is correct |
18 |
Correct |
140 ms |
17740 KB |
Output is correct |
19 |
Correct |
126 ms |
17972 KB |
Output is correct |
20 |
Correct |
87 ms |
13988 KB |
Output is correct |
21 |
Correct |
26 ms |
8636 KB |
Output is correct |
22 |
Correct |
107 ms |
15560 KB |
Output is correct |
23 |
Correct |
107 ms |
16068 KB |
Output is correct |
24 |
Correct |
99 ms |
17448 KB |
Output is correct |
25 |
Correct |
99 ms |
15760 KB |
Output is correct |
26 |
Correct |
124 ms |
19916 KB |
Output is correct |
27 |
Correct |
193 ms |
22032 KB |
Output is correct |
28 |
Correct |
124 ms |
17548 KB |
Output is correct |
29 |
Correct |
170 ms |
20288 KB |
Output is correct |
30 |
Correct |
75 ms |
13904 KB |
Output is correct |
31 |
Correct |
167 ms |
21760 KB |
Output is correct |
32 |
Correct |
109 ms |
17796 KB |
Output is correct |
33 |
Correct |
90 ms |
19632 KB |
Output is correct |
34 |
Correct |
131 ms |
18828 KB |
Output is correct |
35 |
Correct |
98 ms |
17612 KB |
Output is correct |
36 |
Correct |
95 ms |
17072 KB |
Output is correct |
37 |
Correct |
103 ms |
15612 KB |
Output is correct |
38 |
Correct |
98 ms |
19032 KB |
Output is correct |
39 |
Correct |
133 ms |
20528 KB |
Output is correct |
40 |
Correct |
123 ms |
18264 KB |
Output is correct |
41 |
Correct |
105 ms |
16476 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |