#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
const int MAXN = 3e5+5;
const int MAXM = 1e9+5;
const ll inf = (ll)MAXN*MAXM;
ll pre[MAXN];
ll max_dist[MAXN];
pli elems1[MAXN];
pli elems2[MAXN];
int inv[MAXN];
int n;
ll sum(int l, int r) {
return pre[r]-pre[l];
}
pll max(pll a, ll b) {
if (b > a.first) return pll(b, a.first);
if (b > a.second) return pll(a.first, b);
return pll(a.first, a.second);
}
bool makeable(ll cur, vector<int> d, int c) {
vector<ll> mx(4, -inf);
int j = 0;
// priority_queue<int> left;
// priority_queue<int, vector<int>, greater<int>> right;
pll lval(-inf, -inf);
pll rval(-inf, -inf);
ll sum = 0;
for (int i = 0; i < n; i++) {
while (j < n && elems2[j].first > cur+elems1[i].first) {
int v = elems2[j].second;
lval = max(lval, pre[v]+d[v]);
rval = max(rval, d[v]-pre[v]);
j++;
}
int v = elems1[i].second;
ll lv = (lval.first == pre[v]+d[v] && inv[v] < j) ? lval.second : lval.first;
ll rv = (rval.first == d[v]-pre[v] && inv[v] < j) ? rval.second : rval.first;
sum = inf;
mx[0] = max(mx[0], c+d[v]-pre[v]+rv);
mx[1] = max(mx[1], c+d[v]-pre[v]+lv);
mx[2] = max(mx[2], c+d[v]+pre[v]+rv);
mx[3] = max(mx[3], c+d[v]+pre[v]+lv);
}
// assert(mx[0]+mx[1] == -mx[2]-mx[3]);
// ll lv = mx[2]-mx[0], rv = mx[3]-mx[1];
// ll a = min(lv, rv), b = max(lv, rv);
// int lp = 0, rp = 0;
// for (int i = 0; i < n; i++) {
// if (2*pre[i] > b || 2*pre[i] < a) continue;
// while (lp < n && pre[i]-pre[lp]+mx[1] > cur) lp++;
// while (rp < n && -pre[i]+pre[rp]+mx[2] <= cur) rp++;
// if (rp > lp) return 1;
// }
// lp = rp = 0;
// for (int i = n-1; i >= 0; i--) {
// if (2*pre[i] > b || 2*pre[i] < a) continue;
// while (lp < n && pre[i]-pre[lp]+mx[1] > cur) lp++;
// while (rp < n && -pre[i]+pre[rp]+mx[2] <= cur) rp++;
// if (rp > lp) return 1;
// }
for (int i = 0; i < n; i++) {
ll lb = max(mx[1]+pre[i]-cur, mx[3]-pre[i]-cur);
ll ub = min(cur-pre[i]-mx[0], cur+pre[i]-mx[2]);
int mn = -1, mx = n;
while (mx > mn+1) {
int split = (mn+mx)/2;
if (pre[split] <= ub) mn = split;
else mx = split;
}
if (mn >= 0 && pre[mn] >= lb) return 1;
}
return 0;
}
ll find_shortcut(int N, vector<int> l, vector<int> d, int c) {
n = N;
assert(n > 1e5);
for (int i = 1; i < n; i++) pre[i] = pre[i-1]+l[i-1];
for (int i = 0; i < n; i++) {
elems1[i] = pli(pre[i]-d[i], i);
elems2[i] = pli(pre[i]+d[i], i);
}
sort(elems1, elems1+n, greater<pli>());
sort(elems2, elems2+n, greater<pli>());
for (int i = 0; i < n; i++) inv[elems2[i].second] = i;
// max_dist[n-1] = d[n-1];
// int split = n-1;
// ll rdist = max_dist[n-1];
// ll ldist = 0;
// for (int i = n-2; i >= 0; i--) {
// ldist = max(ldist, d[i]+sum(i, split));
// while (split && ldist >= rdist+l[split-1]) {
// split--;
// ldist -= l[split];
// rdist += l[split];
// rdist = max(rdist, (ll)d[split]);
// }
// max_dist[i] = max(ldist, rdist);
// }
ll mn = 0;
ll mx = inf;
makeable(80, d, c);
while (mx > mn+1) {
ll cur = (mn+mx)/2;
if (makeable(cur, d, c)) mx = cur;
else mn = cur;
}
return mx;
}
Compilation message
shortcut.cpp: In function 'bool makeable(ll, std::vector<int>, int)':
shortcut.cpp:38:8: warning: variable 'sum' set but not used [-Wunused-but-set-variable]
38 | ll sum = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
