// moreflags=grader.cpp
#include "meetings.h"
#include<functional>
#include<cassert>
#include<vector>
#include<limits>
//#include<algorithm>
template<class T, class Compare=std::less<T>> struct Maximum{
std::vector<std::vector<T>> data;
Compare compare;
Maximum(){}
template<class F> Maximum(int number, F f, Compare compare_={}){
reset(number, f, compare_);
}
template<class F> void reset(int number, F f, Compare compare_={}){
data.clear(); compare=std::move(compare_);
data.emplace_back(number);
for(int index=0; index<number; ++index)data[0][index]=f(index);
for(int step=1; step<(int)data.back().size(); step<<=1){
auto const& a=data.back();
std::vector<T> b(a.begin(), a.end()-step);
std::transform(begin(b), end(b), begin(a)+step, b.begin(),[&](auto first, auto sec){
return std::max(first, sec, compare);
});
data.push_back(std::move(b));
}
}
T get(int left, int right)const{
auto const layer=31^__builtin_clz(right-left);
return std::max(data[layer][left], data[layer][right-(1<<layer)], compare);
}
};
struct Tree{
std::vector<int64_t> data; // fake tree
void reset(int number){
data.assign(number, 0);
}
void add(int left, int right, int value){
for(int i=left; i<right; ++i) data[i]+=value;
}
void minSegment(int left, int right, int64_t multiplier, int64_t offset){
// actually this function is the hardest to implement in the real implementation, unless there's some special properties of this problem...
for(int i=left; i<right; ++i) data[i]=std::min(data[i], multiplier*i+offset);
}
/*
int64_t minimum(int left, int right){
int64_t result=std::numeric_limits<int64_t>::max();
for(int i=left; i<right; ++i) result=std::min(result, data[i]);
return result;
}
*/
int64_t get(int index){return data[index];}
};
struct Query{int left, right, index;}; // inclusive
struct Solve{
std::vector<int> height, queryLeft, queryRight;
Maximum<std::pair<int, int>> leftHeight, rightHeight;
int maxHeightIndex(int left, int right)const{
// get index with maximum height, or if there's many equal, get the middle most one
// (middle most is not necessary in the full implementation, if any)
if(left+1==right) return left;
int const mid=(left+right)>>1;
auto const [height1, _index1]=leftHeight.get(mid, right);
auto const [height2, index2]=rightHeight.get(left, mid);
auto const index1=-_index1;
assert(mid-index2>0 and index1-mid>=0);
if(height1>height2) return index1;
if(height1<height2) return index2;
if(mid-index2<index1-mid) return index2; else return index1;
}
Tree prefix, suffix;
std::vector<long long> result;
void process(int const left, int const right, std::vector<Query>::iterator first, std::vector<Query>::iterator last){
// left..=right
assert(left<=right);
std::for_each(first, last,[&](auto it){
auto [qleft, qright, _]=it;
assert(left<=qleft and qleft<=qright and qright<=right);
});
if(left==right){
assert(prefix.get(left)==0);
assert(suffix.get(left)==0);
prefix.add(left, left+1, height[left]);
suffix.add(left, left+1, height[left]);
std::for_each(first, last,[&](auto it){
auto [qleft, qright, queryIndex]=it;
assert(left==qleft and left==qright);
result[queryIndex]=height[left];
});
return;
}
auto const mid=maxHeightIndex(left, right+1);
assert(left<=mid); assert(mid<=right);
{
auto const iterator=std::partition(first, last, [&](auto it){return it.right<mid;});
if(left<mid)
process(left, mid-1, first, iterator);
else assert(first==iterator);
first=iterator;
}
{
auto const iterator=std::partition(first, last, [&](auto it){return it.left>mid;});
if(mid<right)
process(mid+1, right, first, iterator);
else assert(first==iterator);
first=iterator;
}
assert(prefix.get(mid)==0); assert(suffix.get(mid)==0);
auto const heightMid=height[mid];
std::for_each(first, last,[&](auto it){
auto [qleft, qright, queryIndex]=it;
assert(left<=qleft and qleft<=mid and mid<=qright and qright<=right);
result[queryIndex]=std::min(
suffix.get(qleft)+int64_t(qright-mid+1)*heightMid,
prefix.get(qright)+int64_t(mid-qleft+1)*heightMid);
});
assert(prefix.get(mid)==0);
prefix.add(mid, right+1, int64_t(mid-left+1)*heightMid);
prefix.minSegment(mid, right+1, heightMid, (mid==left ? 0: prefix.get(mid-1))
-int64_t(mid-1)*heightMid);
assert(suffix.get(mid)==0);
suffix.add(left, mid+1, int64_t(right-mid+1)*heightMid);
suffix.minSegment(left, mid+1, -heightMid, (mid==right ? 0: suffix.get(mid+1))
+int64_t(mid+1)*heightMid);
assert(prefix.get(right)==suffix.get(left));
}
std::vector<long long> solve() {
leftHeight.reset((int)height.size(), [&](auto index){ return std::pair(height[index], -index); });
rightHeight.reset((int)height.size(), [&](auto index){ return std::pair(height[index], index); });
prefix.reset((int)height.size());
suffix.reset((int)height.size());
std::vector<Query> queries(queryLeft.size());
for(int index=0; index<(int)queries.size(); ++index)
queries[index]={queryLeft[index], queryRight[index], index};
result.resize(queries.size());
process(0, (int)height.size()-1, begin(queries), end(queries));
return result;
}
};
std::vector<long long> minimum_costs(std::vector<int> height, std::vector<int> left, std::vector<int> right) {
return Solve{std::move(height), std::move(left), std::move(right)}.solve();
}
