// moreflags=grader.cpp
// 16
// constant optimization is usually not a good idea...
#include "shortcut.h"
#include<vector>
#include<numeric>
#include<algorithm>
#include<cstdint>
#include<climits>
#if not LOCAL
#define NDEBUG
#endif
#include<cassert>
struct T: std::array<int64_t, 4>{
};
struct Tree{ // BIT.
std::vector<T> value;
Tree(int number): value(number, {{INT64_MAX, INT64_MAX, INT64_MAX, INT64_MAX}}){}
static T f(T first, T sec){
std::transform(begin(first), end(first), sec.begin(), first.begin(),
[&](int64_t first, int64_t sec){return std::min(first, sec);});
return first;
}
T minSuffix(int pos) const{
assert(pos>=0); // if pos is too large then INT64_MAX is returned
T result; result.fill(INT64_MAX);
while(pos<(int)value.size()){
result=f(result, value[pos]);
pos|=pos+1;
}
return result;
}
void setMinimum(int pos, T value_){
do{
value[pos]=f(value[pos], value_);
pos&=pos+1; --pos;
}while(pos>=0);
}
};
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
std::vector<int64_t> pos; pos.reserve(n);
pos.push_back(0);
/*
pos.insert(pos.end(), begin(l), end(l));
std::partial_sum(++begin(pos), end(pos), ++pos.begin(), 0);
*/
std::inclusive_scan(begin(l), end(l), std::back_inserter(pos), std::plus<>(), (int64_t)0);
int64_t result{};
for(auto it: l) result+=it;
result+=2**std::max_element(begin(d), end(d));
l.clear();
auto const check=[&](int64_t const result){
auto const process=[&](T initial, auto const f1, auto const f2)->T{
auto const c1=[&](int a){return d[a]-pos[a];};
auto const c2=[&](int b){return +d[b]+pos[b];};
enum class Type{query, set};
struct Event{
int64_t x; int y; Type type; T value;
};
std::vector<Event> events; events.reserve(n*2-1);
for(int a=0; a<n; ++a)
events.push_back({result-c1(a), a+1, Type::query, f1(a)});
for(int b=1; b<n; ++b)
events.push_back({c2(b), b, Type::set, f2(b)});
assert((int)events.size()==n*2-1);
Tree tree(n);
std::sort(begin(events), end(events),[&](Event first, Event sec){
return first.x!=sec.x ? first.x>sec.x: first.type<sec.type;
});
for(auto const [_x, y, type, value]: events){
if(type==Type::query){
auto const tmp=tree.minSuffix(y);
for(int i=0; i<(int)initial.size(); ++i)
if(tmp[i]!=INT64_MAX)
initial[i]=std::min(initial[i], tmp[i]+value[i]);
}else{
assert(type==Type::set);
tree.setMinimum(y, value);
}
}
return initial;
};
T bounds=process(
{{0, INT64_MAX, 0, INT64_MAX}},
[&](int a)->T{return {{
-d[a]-pos[a],
pos[a]-d[a] ,
-d[a]+pos[a],
-pos[a]-d[a]
}};},
[&](int b)->T{return {{
-d[b]-pos[b],
+pos[b]-d[b],
-d[b]-pos[b],
+pos[b]-d[b]
}};}
);
// sum (-minimum, maximum), difference (-minimum, maximum)
if(bounds[1]==INT64_MAX) return true; // no bound. (result >=old diameter)
for(auto& it: bounds) it+=result-c;
bounds[0]=-bounds[0]; bounds[2]=-bounds[2]; // -minimum -> minimum
if(bounds[0]>bounds[1] or bounds[2]>bounds[3]) return false;
for(auto p: pos){
auto const l=std::max(bounds[0]-p, bounds[2]+p), r=std::min(bounds[1]-p, bounds[3]+p);
if(l<=r){
auto const iterator=std::lower_bound(begin(pos), end(pos), l);
if(iterator!=pos.end() and *iterator<=r)
return true; // found a point
}
}
return false;
};
for(int64_t step=(int64_t)1<<(63^__builtin_clzll(result)); step; step>>=1)
if(result-step>0 and check(result-step))
result-=step;
return result;
}
