#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
const int N = (int)1e6 + 10;
ll pl[N];
ll pr[N];
ll cl[N];
ll ml[N];
ll mr[N];
vector<int> l;
vector<int> d;
ll lim;
int n;
ll dim;
struct segment_tree{
ll segt[N * 2];
int sz;
void upd(int id, ll v){
id += sz;
segt[id] = v;
id /= 2;
while(id > 0){
segt[id] = max(segt[id * 2], segt[id * 2 + 1]);
id /= 2;
}
}
ll get(int li, int ri){
li += sz;
ri += sz;
ll val = -(ll)1e18;
while(li <= ri){
if(li % 2 == 1) val = max(val, segt[li ++ ]);
if(ri % 2 == 0) val = max(val, segt[ri -- ]);
li /= 2;
ri /= 2;
}
return val;
}
};
segment_tree rp;
segment_tree lp;
bool check(ll k){ // k < dim by binary search so a shortcut is mandatory
int en = 0;
ll cmp;
for(int i = 0 ;i < n; i ++ ){
if(i + 1 >= n)
cmp = 0ll;
else
cmp = pr[i + 1] + l[i];
cmp += d[i];
if(cmp > k){
rp.upd(i, cl[i] + d[i]);
}
else{
rp.upd(i, -(ll)1e18);
}
}
ll vv;
for(int i = n - 1; i >= 0 ; i -- ){
if(i == 0)
cmp = 0ll;
else
cmp = pl[i - 1] + l[i - 1];
cmp += d[i];
if(cmp > k){
lp.upd(i,-cl[i] + d[i]);
}
else{
lp.upd(i, -(ll)1e18);
}
}
for(int st = 0 ; st < n ; st ++ ){
while(en + 1 < n && (ml[st] > k || mr[en] > k || pl[st] + lim + pr[en] > k)){
en ++ ;
}
if(pl[st] + lim + pr[en] <= k && ml[st] <= k && mr[en] <= k){
// clearly st < en
bool valid = true;
for(int j = st; j <= en; j ++ ){
if((cl[j] - cl[st] + lim + pr[en]) > lim && (cl[en] - cl[j] + pr[en]) > lim){
valid = false;
break;
}
if((cl[j] - cl[st] + pl[st]) > lim && (cl[en] - cl[j] + lim + pl[st]) > lim){
valid = false;
break;
}
}
if(valid) return true;
}
}
return false;
}
ll find_shortcut(int _n, vector<int> _l, vector<int> _d, int _c){
n = _n;
l = _l;
d = _d;
lim = _c;
for(int i = 0 ; i < n; i ++ ){
pl[i]=d[i];
ml[i]=d[i];
if(i>0){
pl[i]=max(pl[i],pl[i-1]+l[i]);
ml[i]=max(ml[i-1],d[i]+l[i-1]+pl[i-1]);
}
}
for(int i = n - 1; i >= 0; i -- ){
pr[i]=d[i];
mr[i]=d[i];
if(i + 1 < n){
pr[i]=max(pr[i],pr[i+1]+l[i]);
mr[i]=max(mr[i+1],d[i]+l[i]+pr[i+1]);
}
}
dim = ml[n-1];
rp.sz = n;
lp.sz = n;
for(int i = 0 ;i + 1 < n; i ++ ){
cl[i + 1] += cl[i] + l[i];
}
ll lf = 0, rf = dim;
ll mid;
while(lf < rf){
mid = (lf + rf) / 2;
if(check(mid))
rf = mid;
else
lf = mid + 1;
}
return rf;
}
Compilation message
shortcut.cpp: In function 'bool check(ll)':
shortcut.cpp:70:8: warning: unused variable 'vv' [-Wunused-variable]
70 | ll vv;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
n = 4, incorrect answer: jury 80 vs contestant 110 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
n = 4, incorrect answer: jury 80 vs contestant 110 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
n = 4, incorrect answer: jury 80 vs contestant 110 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
n = 4, incorrect answer: jury 80 vs contestant 110 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
n = 4, incorrect answer: jury 80 vs contestant 110 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
n = 4, incorrect answer: jury 80 vs contestant 110 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
n = 4, incorrect answer: jury 80 vs contestant 110 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
n = 4, incorrect answer: jury 80 vs contestant 110 |
| 2 |
Halted |
0 ms |
0 KB |
- |
