#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;
struct seg{
ll l, r;
void intersect(seg b){
l = max(l,b.l);
r = min(r,b.r);
}
};
struct smartstack{
vector<pll> v;
ll lz = 0;
void add(ll x){
lz+=x;
}
void push(pll x){
x.ff-=lz;
while(v.size() && v.back().ff <= x.ff)
v.pop_back();
v.push_back(x);
}
pll top(){
if(v.empty())
return {-1,-1};
return {v.back().ff+lz,v.back().ss};
}
void pop(){
v.pop_back();
}
pll operator[](int id){
return {v[id].ff+lz,v[id].ss};
}
int size(){
return v.size();
}
};
ll find_shortcut(int n, vector<int> dist, vector<int> extra, int c){
vector<ll> pref(n);
for(int i = 1; i < n; i++){
pref[i] = dist[i-1]+pref[i-1];
}
vector<ll> bigl(n), bigr(n);
bigl[0] = extra[0];
bigr[n-1] = extra[n-1];
for(int i = 1; i < n; i++){
bigl[i] = max(bigl[i-1]+dist[i-1],(ll)extra[i]);
}
for(int i = n-2; i >= 0; i--){
bigr[i] = max(bigr[i+1]+dist[i],(ll)extra[i]);
}
vector<ll> pairl(n), pairr(n);
for(int i = 1; i < n; i++)
pairl[i] = max(pairl[i-1],bigl[i-1]+extra[i]+dist[i-1]);
for(int i = n-2; i >= 0; i--)
pairr[i] = max(pairr[i+1],bigr[i+1]+extra[i]+dist[i]);
auto test =[&](ll x)->bool{
int minr = n;
while(minr > 0){
if(pairr[minr-1] <= x)
minr--;
else break;
}
bool ok = minr == 0;
for(int l = 0; l < n-1 && pairl[l] <= x && !ok; l++){
// cout << 'a' << endl;
while(minr < n && min(pref[minr]-pref[l],(ll)c) + bigl[l] + bigr[minr] > x)
minr++;
if(minr == n)
break;
int r = minr;
// cout << 'a' << endl;
for(int i = l + 1; i < r; i++){
while(r < n && min(pref[r]-pref[i],pref[i]-pref[l]+c) + extra[i] + bigr[r] > x)
r++;
}
// cout << 'a' << endl;
if(r == n)
continue;
smartstack st;
vector<pll> stvolta;
st.push({bigl[l],l});
stvolta.push_back({bigl[l],l});
// cout << 'a' << endl;
bool curok=1;
for(int i = l+1; i <= r; i++){
// cout << i << endl;
st.add(dist[i-1]);
int unsat1 = -1, unsat2 = st.size()-1;
while(unsat1 !=unsat2){
int m = (unsat1 + unsat2+1)>>1;
if(st[m].ff+extra[i] > x)
unsat1 = m;
else unsat2 = m-1;
}
int sat1 = -1, sat2 = stvolta.size()-1;
while(sat1 !=sat2){
int m = (sat1 + sat2+1)>>1;
if(stvolta[m].ff+extra[i]+pref[r]-pref[i] <= x)
sat1 = m;
else sat2 = m-1;
}
if(unsat1 == -1 || (sat1 != -1 && st[unsat1].ss <= stvolta[sat1].ss)){
st.push({extra[i],i});
if(stvolta.back().ff == extra[i]+pref[i]-pref[l])
stvolta.back().ss++;
else if(stvolta.back().ff < extra[i]+pref[i]-pref[l])
stvolta.push_back({extra[i]+pref[i]-pref[l],i});
} else{
curok = 0;
break;
}
}
ok |= curok;
}
return ok;
};
ll ini = *max_element(all(extra)), fim = pairr[0];
while(ini!=fim){
ll m = (ini+fim)>>1;
if(test(m)){
fim = m;
} else ini = m+1;
}
return ini;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
1 ms |
212 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
1 ms |
212 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
1 ms |
212 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
1 ms |
212 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
1 ms |
212 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
1 ms |
212 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
1 ms |
212 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
n = 4, 80 is a correct answer |
| 2 |
Incorrect |
1 ms |
212 KB |
n = 9, incorrect answer: jury 110 vs contestant 100 |
| 3 |
Halted |
0 ms |
0 KB |
- |
