// moreflags=grader.cpp
// ...
#include "meetings.h"
#include<vector>
#include<cstdint>
#include<algorithm>
#if not LOCAL
#define NDEBUG 1
#endif
#include<cassert>
std::vector<int64_t> solve(std::vector<int> const& height, std::vector<std::pair<int, int>> const& queries_){
// same as minimum_costs, but height[left]==max(height[left..=right]) for (left, right) in queries
struct Query{int left, index;};
std::vector<std::vector<Query>> queries(height.size());
// group queries by right
for(int index=0; index<(int)queries_.size(); ++index){
auto const [left, right]=queries_[index];
queries[right].push_back({left, index});
}
std::vector<int64_t> result(queries_.size());
struct Item{
int64_t value; // extend all the way to the left and right
int64_t leftValue; // value to the left of this block
// (including the "left boundary" of this block, considered outside)
int leftIndex; // index of first item in this block (leftIndex of first block is 0)
int height; // height of "right boundary" of this block (consider inside this block)
};
std::vector<Item> items;
for(int right=0; right<(int)height.size(); ++right){
// now items contains elements with index <right,
// in strictly increasing index and nonstrictly decreasing height order
auto const curHeight=height[right];
auto iterator=items.end();
auto curValue=INT64_MAX;
int64_t const numRightColumn=height.size()-right; // including right itself
while(iterator!=items.begin() and iterator[-1].height<curHeight){
--iterator;
curValue=std::min(curValue,
iterator->value+(curHeight-iterator->height)*numRightColumn);
}
// iterator..items.end() should be deleted
int64_t curLeftValue;
int curLeftIndex;
assert((iterator==items.end())==(curValue==INT64_MAX));
if(iterator==items.end()){
curLeftValue=right==0 ? 0:
items.back().leftValue+int64_t(right-items.back().leftIndex)*items.back().height;
curValue=curLeftValue+curHeight*numRightColumn; // put i at right
curLeftIndex=right;
}else{
// it's not necessary to consider the case i is put at right
curLeftValue=iterator->leftValue;
curLeftIndex=iterator->leftIndex;
}
items.erase(iterator, items.end());
items.push_back({curValue, curLeftValue, curLeftIndex, curHeight});
for(auto [left, queryIndex]: queries[right]){
// since left=max(left..=right), it will be the rightIndex of some block
// so it will be 0 or (x-1) for x some leftIndex
if(left==right){
result[queryIndex]=curHeight;
continue;
}
assert(left<right);
auto iterator=std::lower_bound(begin(items), end(items), left+1, [&](auto const& first, auto const& sec){
return first.leftIndex<sec;
});
assert(iterator[0].leftIndex==left+1);
auto curResult=INT64_MAX;
std::for_each(iterator, items.end(), [&](Item it){
curResult=std::min(curResult, it.value-it.height*(numRightColumn-1));
});
result[queryIndex]=curResult-iterator->leftValue+iterator[-1].height;
}
}
return result;
}
struct MaxQuery{
using T=std::pair<int, int>;
std::vector<std::vector<T>> data;
MaxQuery(std::vector<int> const& value){
data.push_back({}); data[0].resize(value.size());
for(int index=0; index<(int)value.size(); ++index)
data[0][index]={value[index], index};
for(int step=1; step<(int)data.back().size(); step<<=1){
std::vector<T> b(data.back().begin()+step, data.back().end());
std::transform(begin(b), end(b), data.back().begin(), b.begin(),
[&](auto first, auto sec){return std::max(first, sec);});
data.push_back(std::move(b));
}
}
T get(int left, int right)const{
assert(left<right);
int const layer=31^__builtin_clz(right-left);
return std::max(data[layer][left], data[layer][right-(1<<layer)]);
}
};
std::vector<long long> minimum_costs(std::vector<int> height, std::vector<int> left, std::vector<int> right) {
MaxQuery data(height);
std::vector<std::pair<int, int>> queryLeft(left.size()), queryRight(left.size());
for(int index=0; index<(int)left.size(); ++index){
auto const maxIndex=data.get(left[index], right[index]+1).second;
queryLeft[index]={(int)height.size()-1-maxIndex, (int)height.size()-1-left[index]};
queryRight[index]={maxIndex, right[index]};
}
auto const solveLeft=solve(std::vector<int>(height.rbegin(), height.rend()), queryLeft);
auto const solveRight=solve(height, queryRight);
std::vector<long long> result(left.size());
for(int index=0; index<(int)left.size(); ++index){
auto const [maxValue, maxIndex]=data.get(left[index], right[index]+1);
result[index]=std::min(solveLeft[index]+int64_t(right[index]-maxIndex)*maxValue,
solveRight[index]+int64_t(maxIndex-left[index])*maxValue);
}
return result;
}
