//#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll inf = 1e18;
ll find_shortcut(int n, vector<int> l, vector<int> d, int c) {
vector<ll> p(n, 0);
for (int i = 1; i < n; i++) p[i] = p[i - 1] + l[i - 1];
vector<ll> distl(n, 0), distr(n, 0);
ll cur = 0;
for (int i = 0; i < n; i++) {
distl[i] = cur + d[i];
if (i) distl[i] = max(distl[i], distl[i - 1]);
cur = max(cur, (ll)d[i]);
if (i + 1 < n)
cur += l[i];
}
cur = 0;
for (int i = n - 1; i >= 0; i--) {
distr[i] = cur + d[i];
if (i != n - 1) distr[i] = max(distr[i], distr[i + 1]);
cur = max(cur, (ll)d[i]);
if (i)
cur += l[i - 1];
}
ll mxmn = 0;
for (int i = 0; i < n; i++) {
mxmn = max(mxmn, min(distl[i], distr[i]));
}
vector<pair<ll, int>> partl, partr; //partition left, right
ll mud = 0;
for (int i = 0; i < n; i++) {
if (distl[i] == mxmn) {
partl.push_back({ d[i], i });
mud = p[i];
break;
}
if (distr[i] == mxmn) {
partr.push_back({ d[i], i });
mud = p[i];
break;
}
}
for (int i = 0; i < n; i++) {
if (p[i] < mud) partl.push_back({ mud - p[i] + d[i], i });
if (p[i] > mud) partr.push_back({ p[i] - mud + d[i], i });
}
sort(partl.begin(), partl.end());
sort(partr.begin(), partr.end());
ll left = mxmn - 1, right = inf;
while (right - left > 1) {
ll mid = sqrt(left * right);
ll x1 = -inf, x2 = inf, y1 = -inf, y2 = inf;
ll rangl = -inf, rangr = inf;
int cur = partr.size() - 1;
for (int i = 0; i < partl.size(); i++) {
while (cur >= 0 && partr[cur].first + partl[i].first > mid) {
rangl = max(rangl, (ll)p[partr[cur].second] - (mid - c - d[partr[cur].second]));
rangr = min(rangr, (ll)p[partr[cur].second] + (mid - c - d[partr[cur].second]));
//cout << "bruh" << (mid - c - d[partr[cur].second]) << endl;
cur--;
}
// {p[i], rangl}, {p[i], rangr}
//rangr > rangl
//(x, y) -> (x + y, x - y)
rangl += d[partl[i].second]; rangr -= d[partl[i].second];
x1 = max(x1, p[partl[i].second] + rangl);
x2 = min(x2, p[partl[i].second] + rangr);
y1 = max(y1, p[partl[i].second] - rangr);
y2 = min(y2, p[partl[i].second] - rangl);
rangl -= d[partl[i].second]; rangr += d[partl[i].second];
}
for (int i = 0; i < n; i++) {
ll l2 = -inf, r2 = inf;
// x + y > x1, y > x1 - x
l2 = max(l2, x1 - p[i]);
//x + y < x2, y < x2 - x
r2 = min(r2, x2 - p[i]);
//x - y > y1, y < x - y1
r2 = min(r2, p[i] - y1);
//x - y < y2, y > x - y2
l2 = max(l2, p[i] - y2);
if (l2 > r2 || l2 > p.back()) continue;
ll x = *lower_bound(p.begin(), p.end(), l2);
if (x <= r2) goto pass;
}
left = mid;
continue;
pass:;
right = mid;
}
return right;
}
// ll find_shortcut_correct(int n, vector<int> l, vector<int> d, int c) {
// ll res = inf;
// vector<ll> p(n, 0);
// for (int i = 1; i < n; i++) p[i] = p[i - 1] + l[i - 1];
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < n; j++) {
// ll cur = 0;
// for (int a = 0; a < n; a++) {
// for (int b = 0; b < n; b++) {
// cur = max(cur, d[a] + d[b] + min(abs(p[a] - p[b]), abs(p[a] - p[i]) + c + abs(p[a] - p[j])));
// }
// }
// res = min(res, cur);
// }
// }
// return res;
// }
// int main() {
// cout << find_shortcut(4, { 10, 20, 20 }, { 0, 40, 0, 30 }, 10) << endl;
// }
Compilation message
shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:68:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for (int i = 0; i < partl.size(); i++) {
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
n = 4, incorrect answer: jury 80 vs contestant 1000000000000000000 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
n = 4, incorrect answer: jury 80 vs contestant 1000000000000000000 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
n = 4, incorrect answer: jury 80 vs contestant 1000000000000000000 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
n = 4, incorrect answer: jury 80 vs contestant 1000000000000000000 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
n = 4, incorrect answer: jury 80 vs contestant 1000000000000000000 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
n = 4, incorrect answer: jury 80 vs contestant 1000000000000000000 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
n = 4, incorrect answer: jury 80 vs contestant 1000000000000000000 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
n = 4, incorrect answer: jury 80 vs contestant 1000000000000000000 |
| 2 |
Halted |
0 ms |
0 KB |
- |
