#include "shortcut.h"
//Challenge: Accepted
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r){
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 1000005
#define pii pair<ll, ll>
#define ff first
#define ss second
const ll inf = 1LL<<58;
ll p[maxn], lef[maxn], rig[maxn], tmp[maxn], vl[maxn], vr[maxn];
pii ls[maxn], rs[maxn], a[maxn];
long long find_shortcut(int n, vector<int> L, vector<int> D, int C) {
//vector<ll> p(n), lef(n+1, -inf), rig(n+1, -inf), tmp(n), vl(n+1, -inf), vr(n+1, -inf);
//vector<pii> ls(n), rs(n), a(n);
vl[n] = -inf, vr[n] = -inf;
for (int i = 1;i < n;i++) p[i] = p[i-1] + L[i-1];
for (int i = 0;i < n;i++) {
a[i] = {p[i] + D[i], i};
vl[i] = D[i] - p[i];
vr[i] = D[i] + p[i];
}
sort(a, a + n);
for (int i = 0;i < n;i++) {
int id = a[i].ss;
lef[i] = D[id] - p[id];
rig[i] = D[id] + p[id];
ls[i] = {id, n};
rs[i] = {id, n};
}
for (int i = n - 2;i >= 0;i--) {
int se = ls[i].ff;
if (vl[ls[i+1].ff] < vl[se]) {
se = ls[i+1].ff;
} else {
ls[i].ff = ls[i+1].ff;
}
if (vl[se] > vl[ls[i+1].ss]) ls[i].ss = se;
else ls[i].ss = ls[i+1].ss;
se = rs[i].ff;
if (vr[rs[i+1].ff] < vr[se]) {
se = rs[i+1].ff;
} else {
rs[i].ff = rs[i+1].ff;
}
if (vr[se] > vr[rs[i+1].ss]) rs[i].ss = se;
else rs[i].ss = rs[i+1].ss;
}
ll low = 0, up = (1LL<<30) * n * 2;
while (low < up - 1) {
ll M = (low + up) / 2;
ll lb = -inf, rb = inf, db = -inf, ub = inf;
for (int i = 0;i < n-1;i++) {
int ind = upper_bound(rig, rig + n, M - (D[i] - p[i])) - rig;
//[ind, n);
if (ind == n) continue;
ll len = M - D[i] - C;
ll l = (rs[ind].ff != i ? vr[rs[ind].ff] : vr[rs[ind].ss]) - len,
r = -(ls[ind].ff != i ? vl[ls[ind].ff] : vl[ls[ind].ss]) + len;
//square with two points at [l, r]
lb = max(lb, p[i] - r);
rb = min(rb, p[i] - l);
db = max(db, p[i] + l);
ub = min(ub, p[i] + r);
if (rb < lb || ub < db) break;
}
if (rb < lb || ub < db) low = M;
else {
bool good = 0;
int ind = n-1;
for (int i = 0;i < n;i++) {
ll mi = max(db - p[i], -rb + p[i]);
ll ma = min(ub - p[i], -lb + p[i]);
while (ind > 0 && p[ind-1] >= mi) ind--;
if (ind < mi) break;
if (p[ind] >= mi && p[ind] <= ma) {
good = 1;
break;
}
}
ind = n - 1;
for (int i = n - 1;i >= 0;i--) {
ll mi = max(db - p[i], -rb + p[i]);
ll ma = min(ub - p[i], -lb + p[i]);
while (ind > 0 && p[ind-1] >= mi) ind--;
if (ind < mi || good) break;
if (p[ind] >= mi && p[ind] <= ma) {
good = 1;
break;
}
}
if (good) up = M;
else low = M;
}
}
return up;
}
/*
2 4
10
28 37
2 1
3
7 2
*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
n = 4, incorrect answer: jury 80 vs contestant 110 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
n = 4, incorrect answer: jury 80 vs contestant 110 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
n = 4, incorrect answer: jury 80 vs contestant 110 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
n = 4, incorrect answer: jury 80 vs contestant 110 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
n = 4, incorrect answer: jury 80 vs contestant 110 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
n = 4, incorrect answer: jury 80 vs contestant 110 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
n = 4, incorrect answer: jury 80 vs contestant 110 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
n = 4, incorrect answer: jury 80 vs contestant 110 |
| 2 |
Halted |
0 ms |
0 KB |
- |
