#include "shortcut.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
//#define int ll
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pii;
typedef vector<pii> vii;
const int MAX_N = 1e6 + 5;
const ll infinity = 1e18;
ll x[MAX_N];
ll d[MAX_N];
ll c;
int n;
int ind1[MAX_N];
int ind2[MAX_N];
//(i < j)
//xj - xi + di + dj > k -->
//di - xi > k - xj - dj
//di + dj + |xi - y| + |xj - z| + c <= k -->
// (xi - di) + (xj - dj) + (k - c) >= y + z
// (xi + di) + (xj + dj) - (k - c) <= y + z
// (xi - di) - (xj + dj) + (k - c) >= y - z
// (xi + di) - (xj - dj) - (k - c) <= y - z
bool Ok(ll k) {
ll lower_plus = -infinity, lower_minus = -infinity;
ll upper_plus = infinity, upper_minus = infinity;
pii p1 = {-infinity, -infinity}, p2 = {infinity, infinity};
bitset<MAX_N> visited;
for (int j1 = 0, i = 0; j1 < n; j1++) {
int j = ind1[j1];
while (i < n && x[j] + d[j] - (x[ind2[i]] - d[ind2[i]]) > k) {
ll v = x[ind2[i]] + d[ind2[i]];
if (v >= p1.x) {
p1.y = p1.x;
p1.x = v;
} else if (v > p1.y) p1.y = v;
v = x[ind2[i]] - d[ind2[i]];
if (v <= p2.x) {
p2.y = p2.x;
p2.x = v;
} else if (v < p2.y) p2.y = v;
visited[ind2[i]] = true;
i++;
}
ll max_p = p1.x, min_m = p2.x;
if (visited[j] && max_p == x[j] + d[j]) max_p = p1.y;
if (visited[j] && min_m == x[j] - d[j]) min_m = p2.y;
chkmax(lower_plus, max_p + x[j] + d[j] - (k - c));
chkmax(lower_minus, max_p - (x[j] - d[j]) - (k - c));
chkmin(upper_plus, min_m + (x[j] - d[j]) + (k - c));
chkmin(upper_minus, min_m - (x[j] + d[j]) + (k - c));
}
int mid = n;
ll last = infinity;
for (int i = 0; i < n; i++) {
ll z = x[i];
ll lower_y = max(lower_minus + z, lower_plus - z);
if (lower_y > last) {
mid = i;
break;
}
last = lower_y;
}
for (int i = 1, j = 0; i < mid; i++) {
ll z = x[i];
ll lower_y = max(lower_minus + z, lower_plus - z);
ll upper_y = min(upper_minus + z, upper_plus - z);
while (j + 1 < i && x[j + 1] <= upper_y) j++;
if (j != i && x[j] >= lower_y) return true;
}
for (int i = mid, j = 0; i < n; i++) {
ll z = x[i];
ll lower_y = max(lower_minus + z, lower_plus - z);
ll upper_y = min(upper_minus + z, upper_plus - z);
while (j < i && x[j] < lower_y) j++;
if (j != i && x[j] <= upper_y) return true;
}
return false;
}
ll find_shortcut(int32_t N, vector<int32_t> l, vector<int32_t> D, int32_t C) {
n = N;
c = C;
for (int i = 1; i < n; i++) x[i] = x[i - 1] + l[i - 1];
for (int i = 0; i < n; i++) d[i] = D[i], ind1[i] = ind2[i] = i;
sort(ind1, ind1 + n, [&] (int i, int j) {
return x[i] + d[i] < x[j] + d[j];
});
sort(ind2, ind2 + n, [&] (int i, int j) {
return x[i] - d[i] < x[j] - d[j];
});
ll begin = 0, end = 1e18, mid;
ll max_d = 0;
for (int i = 0; i < n; i++) {
chkmax(begin, max_d + d[i]);
chkmax(max_d, ll(d[i]));
}
while (begin < end) {
mid = (begin + end) >> 1;
if (Ok(mid)) {
end = mid;
} else begin = mid + 1;
}
return end;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
340 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
1 ms |
436 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
1 ms |
440 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
1 ms |
340 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
1 ms |
340 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
1 ms |
436 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
1 ms |
440 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
436 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
1 ms |
340 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
1 ms |
340 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
1 ms |
340 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
1 ms |
340 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
1 ms |
340 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
1 ms |
440 KB |
n = 4, 4000000000 is a correct answer |
16 |
Correct |
1 ms |
340 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
1 ms |
444 KB |
n = 10, 1000000343 is a correct answer |
18 |
Correct |
1 ms |
340 KB |
n = 10, 3189 is a correct answer |
19 |
Incorrect |
1 ms |
340 KB |
n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000 |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
340 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
1 ms |
436 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
1 ms |
440 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
1 ms |
340 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
1 ms |
340 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
1 ms |
436 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
1 ms |
440 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
436 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
1 ms |
340 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
1 ms |
340 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
1 ms |
340 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
1 ms |
340 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
1 ms |
340 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
1 ms |
440 KB |
n = 4, 4000000000 is a correct answer |
16 |
Correct |
1 ms |
340 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
1 ms |
444 KB |
n = 10, 1000000343 is a correct answer |
18 |
Correct |
1 ms |
340 KB |
n = 10, 3189 is a correct answer |
19 |
Incorrect |
1 ms |
340 KB |
n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000 |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
340 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
1 ms |
436 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
1 ms |
440 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
1 ms |
340 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
1 ms |
340 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
1 ms |
436 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
1 ms |
440 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
436 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
1 ms |
340 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
1 ms |
340 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
1 ms |
340 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
1 ms |
340 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
1 ms |
340 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
1 ms |
440 KB |
n = 4, 4000000000 is a correct answer |
16 |
Correct |
1 ms |
340 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
1 ms |
444 KB |
n = 10, 1000000343 is a correct answer |
18 |
Correct |
1 ms |
340 KB |
n = 10, 3189 is a correct answer |
19 |
Incorrect |
1 ms |
340 KB |
n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000 |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
340 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
1 ms |
436 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
1 ms |
440 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
1 ms |
340 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
1 ms |
340 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
1 ms |
436 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
1 ms |
440 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
436 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
1 ms |
340 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
1 ms |
340 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
1 ms |
340 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
1 ms |
340 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
1 ms |
340 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
1 ms |
440 KB |
n = 4, 4000000000 is a correct answer |
16 |
Correct |
1 ms |
340 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
1 ms |
444 KB |
n = 10, 1000000343 is a correct answer |
18 |
Correct |
1 ms |
340 KB |
n = 10, 3189 is a correct answer |
19 |
Incorrect |
1 ms |
340 KB |
n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000 |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
340 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
1 ms |
436 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
1 ms |
440 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
1 ms |
340 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
1 ms |
340 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
1 ms |
436 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
1 ms |
440 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
436 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
1 ms |
340 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
1 ms |
340 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
1 ms |
340 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
1 ms |
340 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
1 ms |
340 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
1 ms |
440 KB |
n = 4, 4000000000 is a correct answer |
16 |
Correct |
1 ms |
340 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
1 ms |
444 KB |
n = 10, 1000000343 is a correct answer |
18 |
Correct |
1 ms |
340 KB |
n = 10, 3189 is a correct answer |
19 |
Incorrect |
1 ms |
340 KB |
n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000 |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
340 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
1 ms |
436 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
1 ms |
440 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
1 ms |
340 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
1 ms |
340 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
1 ms |
436 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
1 ms |
440 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
436 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
1 ms |
340 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
1 ms |
340 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
1 ms |
340 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
1 ms |
340 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
1 ms |
340 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
1 ms |
440 KB |
n = 4, 4000000000 is a correct answer |
16 |
Correct |
1 ms |
340 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
1 ms |
444 KB |
n = 10, 1000000343 is a correct answer |
18 |
Correct |
1 ms |
340 KB |
n = 10, 3189 is a correct answer |
19 |
Incorrect |
1 ms |
340 KB |
n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000 |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
340 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
1 ms |
436 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
1 ms |
440 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
1 ms |
340 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
1 ms |
340 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
1 ms |
436 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
1 ms |
440 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
436 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
1 ms |
340 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
1 ms |
340 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
1 ms |
340 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
1 ms |
340 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
1 ms |
340 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
1 ms |
440 KB |
n = 4, 4000000000 is a correct answer |
16 |
Correct |
1 ms |
340 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
1 ms |
444 KB |
n = 10, 1000000343 is a correct answer |
18 |
Correct |
1 ms |
340 KB |
n = 10, 3189 is a correct answer |
19 |
Incorrect |
1 ms |
340 KB |
n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000 |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
n = 4, 80 is a correct answer |
2 |
Correct |
2 ms |
340 KB |
n = 9, 110 is a correct answer |
3 |
Correct |
1 ms |
436 KB |
n = 4, 21 is a correct answer |
4 |
Correct |
1 ms |
440 KB |
n = 3, 4 is a correct answer |
5 |
Correct |
1 ms |
340 KB |
n = 2, 62 is a correct answer |
6 |
Correct |
1 ms |
340 KB |
n = 2, 3 is a correct answer |
7 |
Correct |
1 ms |
436 KB |
n = 3, 29 is a correct answer |
8 |
Correct |
1 ms |
440 KB |
n = 2, 3 is a correct answer |
9 |
Correct |
1 ms |
436 KB |
n = 2, 3 is a correct answer |
10 |
Correct |
1 ms |
340 KB |
n = 2, 2000000001 is a correct answer |
11 |
Correct |
1 ms |
340 KB |
n = 2, 3000000000 is a correct answer |
12 |
Correct |
1 ms |
340 KB |
n = 3, 3000000000 is a correct answer |
13 |
Correct |
1 ms |
340 KB |
n = 3, 3000000000 is a correct answer |
14 |
Correct |
1 ms |
340 KB |
n = 4, 3000000001 is a correct answer |
15 |
Correct |
1 ms |
440 KB |
n = 4, 4000000000 is a correct answer |
16 |
Correct |
1 ms |
340 KB |
n = 5, 4000000000 is a correct answer |
17 |
Correct |
1 ms |
444 KB |
n = 10, 1000000343 is a correct answer |
18 |
Correct |
1 ms |
340 KB |
n = 10, 3189 is a correct answer |
19 |
Incorrect |
1 ms |
340 KB |
n = 10, incorrect answer: jury 7000000000 vs contestant 6000000000 |
20 |
Halted |
0 ms |
0 KB |
- |