Submission #299772

#	Time	Username	Problem	Language	Result	Execution time	Memory
299772		user202729	Meetings (IOI18_meetings)	C++17	60 / 100	5521 ms	211504 KiB

meetings

// moreflags=grader.cpp
// it's a little unexpected that the previous solution pass subtask 3 and 4.
#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 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;

	struct Item2{
		int rightIndex;
		int height; // ==height[rightIndex]
		int64_t value;
	};
	std::vector<Item2> items2; // strictly increasing rightIndex, nonstrictly decreasing height,
	// sloped-decreasing value (maintained with something else)

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

		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.back().rightIndex>=curLeftIndex)
			items2.pop_back();
		items2.push_back({right, height[right], curValue});

		// naively maintain items2
		assert(not items2.empty());
		auto out=items2.begin()+1;
		std::for_each(out, items2.end(), [&](Item2 it){
			assert(out[-1].rightIndex<it.rightIndex);
			while(out!=items2.begin() and
					out[-1].value-int64_t(numRightColumn-1)*out[-1].height
					>=
					it.value-int64_t(numRightColumn-1)*it.height
			  ){
				--out;
			}
			*out++=it;
		});
		items2.erase(out, items2.end());

		// 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=std::upper_bound(begin(items2), end(items2), left,
						[&](auto const& first, auto const& sec){
							return first<sec.rightIndex;
						});
				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;
}

Compilation message (stderr)

meetings.cpp: In function 'std::vector<long int> solve(const std::vector<int>&, const std::vector<std::pair<int, int> >&)':
meetings.cpp:109:15: warning: variable 'naiveMinSlopedValue' set but not used [-Wunused-but-set-variable]
  109 |    auto const naiveMinSlopedValue=[&]{
      |               ^~~~~~~~~~~~~~~~~~~

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