#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> pii;
#define fi first
#define se second
#define mp make_pair
const int N = (int)1e6 + 10;
int n;
ll X[N];
vector<ll> W;
ll L;
vector<pii> A,B;
bool check(ll k){
ll mx = 0;
for(int i = 0 ; i < n; i ++ ){
if(W[i] + mx > k) return false;
mx = max(mx, W[i]);
}
ll lowplus = -(ll)1e18;
ll highplus = (ll)1e18;
ll lowminus = -(ll)1e18;
ll highminus = (ll)1e18;
/*
for(int i = 0 ; i < n; i ++ ){
for(int j = 0; j < n; j ++ ){
if(i == j) continue;
if(X[j] + W[j] - (X[i] - W[i]) <= k) continue; // no one cares
lowplus = max(lowplus, -k + X[i] + X[j] + L + W[i] + W[j]);
highplus = min(highplus, k + X[i] + X[j] - L - W[i] - W[j]);
lowminus = max(lowminus, -k + X[i] - X[j] + L + W[i] + W[j]);
highminus = min(highminus, k + X[i] - X[j] - L - W[i] - W[j]);
}
}
*/
int pi = 0;
int i,j;
ll extra;
ll H[2];
pii P0, P1;
P0 = P1 = mp(-(ll)1e18, -1);
pii M0, M1;
M0 = M1 = mp((ll)1e18, -1);
for(int ii = 0 ; ii < n; ii ++ ){
//H[0] = -(ll)1e18;
//H[1] = (ll)1e18;
j = A[ii].se;
/*
for(int jj = 0 ; jj < n; jj ++ ){
if(A[ii].fi - B[jj].fi <= k) break;
if(A[ii].se == B[jj].se) continue;
i = B[jj].se;
H[0] = max(H[0], X[i] + W[i]);
H[1] = min(H[1], X[i] - W[i]);
}
lowplus = max(lowplus, -k + H[0] + X[j] + L + W[j]);
highplus = min(highplus, k + H[1] + X[j] - L - W[j]);
lowminus = max(lowminus, -k + H[0] - X[j] + L + W[j]);
highminus = min(highminus, k + H[1] - X[j] - L - W[j]);
*/
while(pi < n && A[i].fi - B[pi].fi > k){
i = B[pi].se;
if(mp(X[i] + W[i], i) > P0){
P1 = P0;
P0 = mp(X[i] + W[i], i);
}
else if(mp(X[i] + W[i], i) > P1){
P1 = mp(X[i] + W[i], i);
}
if(mp(X[i] - W[i], i) < M0){
M1 = M0;
M0 = mp(X[i] - W[i], i);
}
else if(mp(X[i] - W[i], i) < M1){
M1 = mp(X[i] - W[i], i);
}
pi ++ ;
}
if(j == P0.se) i = P1.se;
else i = P0.se;
if(i != -1){
lowplus = max(lowplus, -k + X[i] + W[i] + X[j] + L + W[j]);
lowminus = max(lowminus, -k + X[i] + W[i] - X[j] + L + W[j]);
}
if(j == M0.se) i = M1.se;
else i = M0.se;
if(i != -1){
highplus = min(highplus, k + X[i] - W[i] + X[j] - L - W[j]);
highminus = min(highminus, k + X[i] - W[i] - X[j] - L - W[j]);
}
}
int i0 = n - 1, j0 = n - 1;
int i1 = 0, j1 = 0;
int tl, tr;
for(int i = 0 ; i < n; i ++ ){
while(i0 >= 0 && X[i] + X[i0] > highplus){
i0 -- ;
}
while(j0 > 0 && X[i] + X[j0 - 1] >= lowplus){
j0 -- ;
}
while(i1 < n && X[i] - X[i1] > highminus){
i1 ++ ;
}
while(j1 + 1 < n && X[i] - X[j1 + 1] >= lowminus){
j1 ++ ;
}
tl = i + 1;
tr = n - 1;
tl = max(tl, j0);
tr = min(tr, i0);
tl = max(tl, i1);
tr = min(tr, j1);
if(tl <= tr){
return true;
}
}
return false;
}
ll find_shortcut(int _n, vector<int> l, vector<int> _d, int _c){
n = _n;
for(int i = 1; i < n; i ++ ){
X[i] = X[i - 1] + l[i - 1];
}
for(auto x : _d)
W.push_back(x);
for(int i = 0 ; i < n; i ++ ){
A.push_back(mp(X[i] + W[i], i));
B.push_back(mp(X[i] - W[i] ,i));
}
sort(A.begin(), A.end());
sort(B.begin(), B.end());
L = _c;
ll li = 0;
ll ri = (ll)1e16;
ll mid;
while(li < ri){
mid = (li + ri) / 2;
if(check(mid)){
ri = mid;
}
else{
li = mid + 1;
}
}
return li;
}
Compilation message
shortcut.cpp: In function 'bool check(ll)':
shortcut.cpp:45:8: warning: unused variable 'extra' [-Wunused-variable]
45 | ll extra;
| ^~~~~
shortcut.cpp:46:8: warning: unused variable 'H' [-Wunused-variable]
46 | ll H[2];
| ^
shortcut.cpp:70:28: warning: 'i' may be used uninitialized in this function [-Wmaybe-uninitialized]
70 | while(pi < n && A[i].fi - B[pi].fi > k){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
