// moreflags=grader.cpp
// what have I done...
// :(
// 17
#ifndef LOCAL
#define NDEBUG 1
#endif
#include<bits/stdc++.h>
#include "walk.h"
long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r,
std::vector<int> y, int s, int g) {
//int64_t result=INT64_MAX;
struct Segment{
int left, right;
};
std::map<int, std::vector<Segment>> segments;
for(int index=0; index<(int)y.size(); ++index)
segments[y[index]].push_back({l[index], r[index]});
for(auto& [_y, it]: segments){
assert(not it.empty());
std::sort(begin(it), end(it),[&](auto first, auto sec){return first.left<sec.left;});
auto out=++it.begin();
std::for_each(out, it.end(),[&](auto segment){
assert(out[-1].right<=segment.left);
assert(segment.left<segment.right);
if(out[-1].right==segment.left)
out[-1].right=segment.right;
else
*out++=segment;
});
it.erase(out, it.end());
}
y.clear(); l.clear(); r.clear();
auto const n=(int)x.size();
if(s==0 and g==n-1){
struct Event{ int y, index; bool open; };
std::vector<Event> events;
for(auto const& [y, it]: segments){
for(auto const it: it){
events.push_back({y, it.left, true});
if(it.right!=n-1)
events.push_back({y, it.right, false});
}
}
events.push_back({0, 0, false});
std::sort(begin(events), end(events),[&](Event first, Event sec){
return first.index!=sec.index ? first.index>sec.index: first.open<sec.open;
// reverse(increasing index->open before close)
});
std::set<int> have; //{y}
std::map<int, int64_t> value;
std::set<int> unstable;
have.insert(0);
value[0]=0;
for(int index=0; index<(int)x.size();++index){
auto const curHeight=h[index];
while(not unstable.empty()){ // smoothen part <= curHeight
auto const pos=*unstable.begin();
if(pos>curHeight) break;
unstable.erase(unstable.begin());
auto const iterator=value.find(pos);
while(iterator!=value.begin()){
auto const prev=std::prev(iterator);
if(prev->second > iterator->second+iterator->first-prev->first)
value.erase(prev);
else
break;
}
}
if(auto const iterator=have.upper_bound(curHeight);
iterator!=have.end()) unstable.insert(*iterator);
while(not events.empty() and events.back().index==index){
auto const [y, index_, open]=events.back(); events.pop_back();
assert(index==index_);
assert(y<=curHeight);
if(open){
{
auto const [iterator, inserted]=have.insert(y);
assert(inserted);
}
{
auto const [iterator, inserted]=value.insert({y, 0});
assert(inserted);
int64_t curValue=INT64_MAX/2;
if(iterator!=value.begin()){
auto [y_, value1]=*std::prev(iterator);
assert(y_<y);
curValue=y-y_+value1;
}
if(std::next(iterator)!=value.end()){
auto [y_, value1]=*std::next(iterator);
if(y_<=curHeight)
curValue=std::min(curValue, y_-y+value1);
}
iterator->second=curValue;
}
}else{
auto const curHave=have.erase(have.find(y));
auto curValue=value.find(y);
if(curValue!=value.end()){
auto const curValue_=curValue->second;
auto const nextValue=value.erase(curValue);
if(curHave!=have.begin()){
auto const prevHave=std::prev(curHave);
auto const newValue_=curValue_+y-*prevHave;
auto const newValueIterator=value.insert(nextValue, {*prevHave, newValue_});
// do nothing if *prevHave already exists in value
}
}
}
}
}
auto const result=(value.empty() ? INT64_MAX/2: value.begin()->first+value.begin()->second)
+x.back()-x[0];
return result>=INT64_MAX/2 ? -1: result;
}
__builtin_trap();
//return (result==INT64_MAX ? -1: result);
}
