// moreflags=grader.cpp
// 17
#ifndef LOCAL
#define NDEBUG 1
#endif
#include<bits/stdc++.h>
#include "walk.h"
struct Value{
std::set<int> have; //{y}
std::map<int, int64_t> value;
std::set<int> unstable;
Value(){
have.insert(0);
value[0]=0;
}
void smoothen(int const curHeight){
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=value.upper_bound(curHeight);
iterator!=value.end()) unstable.insert(iterator->first);
}
void addOpen(int y, int curHeight){
auto const [haveIterator, haveInserted]=have.insert(y);
assert(haveInserted);
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)
if(*std::next(haveIterator)<=curHeight)
curValue=std::min(curValue, y_-y+value1);
}
iterator->second=curValue;
}
void addClose(int y){
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
}
}
assert(not unstable.count(y));
}
static void minimize(int y, Value& first, Value& sec, int offset1, int offset2){
}
};
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;
if(s>g) std::swap(s, g);
auto const n=(int)x.size();
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]});
std::array<std::map<int, std::vector<Segment>>, 3> parts;
std::array<std::vector<std::pair<int, Segment>>, 2> tops;
std::set<int> remaining;
std::vector<std::pair<int, int>> heights(n);
for(int it=0; it<n; ++it){
remaining.insert(remaining.end(), it);
heights[it]={h[it], it};
}
std::sort(begin(heights), end(heights),[&](auto first, auto sec){return first.first>sec.first;});
for(auto& [y, it]: segments){
while(not heights.empty() and heights.back().first<y){
remaining.erase(remaining.find(heights.back().second));
heights.pop_back();
}
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());
for(auto [left, right]: it){
assert(remaining.count(left));
assert(remaining.count(right));
assert(left<right);
for(int i=0; i<2; ++i){
if(left==right) break;
auto const cut=i==0 ? s: g;
if(i==1) assert(left>=s);
if(left<right and left<cut){
auto iterator=remaining.upper_bound(cut);
auto const right1=right<=cut ? right: *std::prev(iterator);
assert(left<=right1);
if(left<right1){
parts[i][y].push_back({left, right1});
left=right1;
}
if(left<right and left<cut){
if(i==1){
assert(left>=s); assert(*iterator>g);
}
tops[i].push_back({y, {left, *iterator}});
left=*iterator;
assert(left<=right);
}
}
}
assert(left<=right);
if(left<right){
assert(left>=g);
parts[2][y].push_back({left, right});
left=right;
}
}
}
tops[0].push_back({INT_MAX, {0, n-1}});
for(auto& it: tops) assert(std::is_sorted(begin(it), end(it),
[&](auto first, auto sec){return first.first<sec.first;}));
y.clear(); l.clear(); r.clear();
enum class Type{ open, close };
struct Event{ int y, index; Type type; };
std::array<std::vector<Event>, 2> events;
for(auto const& [y, it]: parts[1]){
for(auto const it: it){
events[1].push_back({y, it.left, Type::open});
events[1].push_back({y, it.right, Type::close});
}
}
events[1].push_back({0, s, Type::close});
events[1].push_back({0, g, Type::open});
std::sort(begin(events[1]), end(events[1]),[&](Event first, Event sec){
return first.index!=sec.index ? first.index>sec.index: first.type>sec.type;
// reverse(increasing index->open before close)
});
for(auto const& [y, it]: parts[0]){
for(auto const it: it){
events[0].push_back({y, it.right, Type::open});
events[0].push_back({y, it.left, Type::close});
}
}
events[0].push_back({0, s, Type::close});
events[0].push_back({0, 0, Type::open});
std::sort(begin(events[0]), end(events[0]),[&](Event first, Event sec){
return first.index!=sec.index ? first.index<sec.index: first.type>sec.type;
// reverse(decreasing index->open before close)
});
/*
std::array<int, 2> bounds{{s, s}};
std::array<Value, 2> value;
auto const process=[&](Value& value, int const index, std::vector<Event>& events){
auto const curHeight=h[index];
value.smoothen(curHeight);
while(not events.empty() and events.back().index==index){
auto const [y, index_, type]=events.back(); events.pop_back();
assert(index==index_);
assert(y<=curHeight);
if(type==Type::open){
value.addOpen(y, curHeight);
}else{
assert(type==Type::close);
value.addClose(y);
}
}
};
for(auto const [y, leftRight]: tops[0]){
auto const [left, right]=leftRight;
assert(bounds[0]>=left);
while(bounds[0]>left){
process(value[0], --bounds[0], events[0]);
}
assert(bounds[1]<=right);
while(bound[1]<right){
process(value[1], ++bounds[1], events[1]);
}
Value::minimize(y, value[0], value[1], x[s]-x[left], x[right]-x[s]);
}
for(int index=0; index<(int)x.size();++index){
}
*/
if(s==0 and g==n-1){
std::vector<Event> events;
for(auto const& [y, it]: segments){
for(auto const it: it){
events.push_back({y, it.left, Type::open});
events.push_back({y, it.right, Type::close});
}
}
events.push_back({0, 0, Type::close});
events.push_back({0, n-1, Type::open});
std::sort(begin(events), end(events),[&](Event first, Event sec){
return first.index!=sec.index ? first.index>sec.index: first.type>sec.type;
// reverse(increasing index->open before close)
});
Value value;
for(int index=0; index<(int)x.size();++index){
auto const curHeight=h[index];
value.smoothen(curHeight);
while(not events.empty() and events.back().index==index){
auto const [y, index_, type]=events.back(); events.pop_back();
assert(index==index_);
assert(y<=curHeight);
if(type==Type::open){
value.addOpen(y, curHeight);
}else{
assert(type==Type::close);
value.addClose(y);
}
}
}
assert(value.value.size()==1);
assert(value.value.begin()->first==0);
auto const result=value.value.begin()->second+(x.back()-x[0]);
return result>=INT64_MAX/2 ? -1: result;
}
__builtin_trap();
}
