#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c) {
vector<int64_t> a(n), b(n); // a = x + d, b = x - d
vector<int64_t> x(n);
for (int i = 1; i < n; i++) x[i] = x[i - 1] + l[i - 1];
for (int i = 0; i < n; i++) a[i] = x[i] + d[i], b[i] = x[i] - d[i];
vector<int64_t> dx = x;
for (auto& v : dx) v *= 2;
// abs(x[i] - x[p]) + abs(x[j] - x[q]) + d[i] + d[j] + c <= target
// x[i] - x[p] + x[j] - x[q] + d[i] + d[j] + c <= target
// x[p] - x[i] + x[j] - x[q] + d[i] + d[j] + c <= target
// x[i] - x[p] + x[q] - x[j] + d[i] + d[j] + c <= target
// x[p] - x[i] + x[q] - x[j] + d[i] + d[j] + c <= target
// x[p] + x[q] >= x[i] + x[j] + d[i] + d[j] + c - target
// x[p] + x[q] <= x[i] + x[j] - d[i] - d[j] - c + target
// x[q] - x[p] <= x[j] - x[i] - d[i] - d[j] - c + target
// x[q] - q[p] >= x[j] - x[i] + d[i] + d[j] + c - target
// k := c - target
// x[p] + x[q] >= (x[i] + d[i]) + (x[j] + d[j]) + k
// x[p] + x[q] <= (x[i] - d[i]) + (x[j] - d[j]) - k
// x[q] - x[p] <= (x[j] - d[j]) - (x[i] + d[i]) - k
// x[q] - x[p] >= (x[j] + d[j]) - (x[i] - d[i]) + k
// x[p] + x[q] >= a[i] + a[j] + k
// x[p] + x[q] <= b[i] + b[j] - k
// x[q] - x[p] <= b[j] - a[i] - k
// x[q] - x[p] >= a[j] - b[i] + k
auto check = [&](int64_t target) {
int64_t low_sum = -1e18, high_sum = +1e18;
int64_t low_diff = -1e18, high_diff = +1e18;
int64_t k = c - target;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (x[j] - x[i] + d[i] + d[j] > target) {
low_sum = max(low_sum, a[i] + a[j] + k);
high_sum = min(high_sum, b[i] + b[j] - k);
low_diff = max(low_diff, a[j] - b[i] + k);
high_diff = min(high_diff, b[j] - a[i] - k);
}
}
}
if (low_sum > high_sum || low_diff > high_diff) return 0;
int low_sum_q = 0, low_diff_q = 0, high_sum_q = 0, high_diff_q = 0;
for (int p = 0; p < n; p++) {
low_sum_q = max(low_sum_q, p + 1);
low_diff_q = max(low_diff_q, p + 1);
while (low_sum_q < n && x[p] + x[low_sum_q] < low_sum) low_sum_q++;
while (high_sum_q < n && x[p] + x[high_sum_q] <= high_sum) high_sum_q++;
// [low_sum_q, high_sum_q)
while (low_diff_q < n && x[low_diff_q] - x[p] < low_diff) low_diff_q++;
while (high_diff_q < n && x[high_diff_q] - x[p] <= high_diff) high_diff_q++;
// [low_diff_q, high_diff_q)
if (low_sum_q >= high_sum_q || low_diff_q >= high_diff_q) continue;
if (low_sum_q < high_diff_q || low_diff_q < high_sum_q) return 1;
}
return 0;
};
int64_t low = 0, high = 1ll << 60;
while (low < high) {
int64_t mid = low + high >> 1;
if (check(mid)) {
high = mid;
} else {
low = mid + 1;
}
}
return high;
}
Compilation message
shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:72:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
72 | int64_t mid = low + high >> 1;
| ~~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
n = 4, incorrect answer: jury 80 vs contestant 90 |
| 2 |
Halted |
0 ms |
0 KB |
- |
