#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())
#ifdef LOCAL
#include <print.h>
#else
#define trace(...)
#define endl '\n'
#endif
const int N = 1 << 20;
const ll INF = 1e18;
struct Data{
ll a, b;
Data() : a(-INF), b(INF){}
Data(ll a, ll b) : a(a), b(b){}
};
inline void merge(Data & X, const Data & Y){
X.a = max(X.a, Y.a);
X.b = min(X.b,Y.b);
}
Data prefix[N];
ll p[N];
int perm1[N], perm2[N];
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c){
for(int i = 1; i < n; i++) p[i] = p[i - 1] + l[i - 1];
iota(perm1, perm1 + n, 0);
iota(perm2, perm2 + n, 0);
sort(perm1, perm1 + n, [&](int i, int j){return d[i] - p[i] > d[j] - p[j];});
sort(perm2, perm2 + n, [&](int i, int j){return d[i] + p[i] < d[j] + p[j];});
int mx = 0, mx2 = 0, ind_mx = 0;
for(int i = 1; i <= n; i++){
int ind = perm1[i - 1];
prefix[i] = prefix[i - 1];
merge(prefix[i], Data(p[ind] + d[ind], p[ind] - d[ind]));
if(d[ind] > mx){
mx2 = mx;
mx = d[ind];
ind_mx = ind;
} else if(d[ind] > mx2) mx2 = d[ind];
}
ll lo = mx + mx2, hi = p[n - 1] / 2 + 2e9; // (t - d) / 2 = L - t -> 3*t = 2 * L + d, (L - d) / 3
lo = max(lo, (p[n - 1] - 1000000000) / 3);
while(lo < hi){
ll D = (lo + hi) / 2;
Data d1, d2;
int cur = 0;
for(int i : perm2){
while(cur < n && d[perm1[cur]] + d[i] + p[i] - p[perm1[cur]] > D) cur++;
Data temp = prefix[cur];
if(D < 2 * mx && i == ind_mx){
temp = Data();
for(int r = 0; r < cur; r++){
int _r = perm1[r];
if(_r == i) continue;
merge(temp, Data(p[_r] + d[_r], p[_r] - d[_r]));
}
}
d1.a = max(d1.a, temp.a + d[i] + c - p[i] - D);
d1.b = min(d1.b, temp.b - d[i] - c - p[i] + D);
d2.a = max(d2.a, temp.a + p[i] - D + d[i] + c);
d2.b = min(d2.b, temp.b + p[i] + D - d[i] - c);
}
ll L1 = d1.a, R1 = d1.b;
ll L2 = d2.a, R2 = d2.b;
if(L1 > R1 || L2 > R2){
lo = D + 1;
continue;
}
bool ok = false;
int ptr1 = 0;
int ptr2 = n;
for(int v = 1; v < n; v++){
while(ptr1 < n && p[ptr1] - p[v] < L1) ptr1++;
while(ptr2 > 0 && p[ptr2 - 1] + p[v] >= L2) ptr2--;
int u = max(ptr1, ptr2);
if(u >= v) continue;
if(p[u] - p[v] > R1 || p[u] + p[v] > R2) continue;
ok = true;
break;
}
if(ok) hi = D;
else lo = D + 1;
}
return lo;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
270 ms |
16728 KB |
n = 4, incorrect answer: jury 80 vs contestant 100 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
270 ms |
16728 KB |
n = 4, incorrect answer: jury 80 vs contestant 100 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
270 ms |
16728 KB |
n = 4, incorrect answer: jury 80 vs contestant 100 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
270 ms |
16728 KB |
n = 4, incorrect answer: jury 80 vs contestant 100 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
270 ms |
16728 KB |
n = 4, incorrect answer: jury 80 vs contestant 100 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
270 ms |
16728 KB |
n = 4, incorrect answer: jury 80 vs contestant 100 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
270 ms |
16728 KB |
n = 4, incorrect answer: jury 80 vs contestant 100 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
270 ms |
16728 KB |
n = 4, incorrect answer: jury 80 vs contestant 100 |
| 2 |
Halted |
0 ms |
0 KB |
- |
