// moreflags=grader.cpp
// without transparent comparator.
// a little easier to implement.
#include "meetings.h"
#include<vector>
#include<cstdint>
#include<climits>
#include<map>
#include<algorithm>
#include<set>
#if not LOCAL
#define NDEBUG 1
#endif
#include<cassert>
struct Item2;
using Changes=std::multimap<int, std::set<Item2>::iterator>;
struct Item2{
int rightIndex;
int height; // ==height[rightIndex]
int64_t value;
mutable Changes::iterator change; // to destroy this element
bool operator<(Item2 const& other) const{return rightIndex<other.rightIndex;}
};
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 rightIndex; // index of last (inclusive) item in this block
int height; // height[rightIndex] (consider inside this block) also == maximum height of block
};
std::vector<Item> items;
Changes changes;
std::set<Item2> items2; // strictly increasing rightIndex, nonstrictly decreasing height,
// sloped-decreasing value (maintained with something else)
auto const popItems2=[&]{
auto iterator=--items2.end();
assert(iterator->change==changes.end());
items2.erase(iterator);
if(items2.empty()) return;
iterator=--items2.end();
if(iterator->change!=changes.end()){
changes.erase(iterator->change);
iterator->change=changes.end();
}
};
auto const constructChange=[&](std::set<Item2>::iterator first, Item2 sec)->Changes::iterator{
assert(first->rightIndex<sec.rightIndex);
if(sec.value>first->value) return changes.end();
return changes.emplace(
first->height==sec.height ? INT_MAX: (first->value-sec.value)/(first->height-sec.height)
, first);
};
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
auto const insertItems2=[&](Item2 const value){
assert(value.change==changes.end());
while(not items2.empty() and
items2.rbegin()->value-int64_t(numRightColumn-1)*items2.rbegin()->height
>=
value.value-int64_t(numRightColumn-1)*value.height
){
popItems2();
}
auto const oldSize=items2.size();
std::set<Item2>::iterator iterator=items2.insert(items2.end(), value);
assert(items2.size()==oldSize+1);
if(items2.size()==1) return;
--iterator;
assert(iterator->change==changes.end());
//std::set<Item2>::iterator tmp=iterator;
iterator->change=constructChange(iterator, value);
};
auto const maintainItems2=[&]{
while(not changes.empty()){
auto const iterator=--changes.end();
if(iterator->first<numRightColumn-1) break;
std::set<Item2>::iterator const iterator2=iterator->second;
changes.erase(iterator);
auto const iterator3=items2.erase(iterator2);
if(iterator3==items2.begin()) continue;
auto const iterator4=std::prev(iterator3);
if(iterator4->change!=changes.end())
changes.erase(iterator4->change);
iterator4->change=iterator3==items2.end() ? changes.end(): constructChange(iterator4,*iterator3);
}
};
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;
}
for(auto _=items.end()-iterator; _--;)
items.pop_back();
items.push_back({curValue, curLeftValue, curLeftIndex, right, curHeight});
// handle push/pop changes to items2
while(not items2.empty() and items2.rbegin()->rightIndex>=curLeftIndex)
popItems2();
insertItems2({right, height[right], curValue, changes.end()});
maintainItems2();
// handle queries
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 const 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 const naiveMinSlopedValue=[&]{
auto curResult=INT64_MAX;
std::for_each(iterator, items.end(), [&](Item it){
curResult=std::min(curResult, it.value-it.height*(numRightColumn-1));
});
return curResult;
};
auto const smartMinSlopedValue=[&]{
auto iterator=items2.upper_bound({left});
return iterator->value-iterator->height*(numRightColumn-1);
};
assert(([&]{
auto const tmp=naiveMinSlopedValue();
auto const tmp2=smartMinSlopedValue();
assert(tmp==tmp2);
return true;
}()));
result[queryIndex]=smartMinSlopedValue()-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;
}
