Submission #299736

#	Time	Username	Problem	Language	Result	Execution time	Memory
299736		user202729	Meetings (IOI18_meetings)	C++17	60 / 100	5526 ms	209572 KiB

meetings

// 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;
}

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 0 / 40