Submission #299897

#	Time	Username	Problem	Language	Result	Execution time	Memory
299897		user202729	Meetings (IOI18_meetings)	C++17	100 / 100	2751 ms	220612 KiB

meetings

// moreflags=grader.cpp
// without mutable or const_cast.
// perhaps not much faster (std::map is implemented approximately like this too), but simpler.
#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::map<int, Item2>::iterator>;
struct Item2{
	int height; // ==height[rightIndex]
	int64_t value;
	Changes::iterator change; // to destroy this element
};

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::map<int, Item2> items2; // strictly increasing rightIndex, nonstrictly decreasing height,
	// sloped-decreasing value (maintained with something else)

	auto const popItems2=[&]{
		auto iterator=--items2.end();
		assert(iterator->second.change==changes.end());
		items2.erase(iterator);
		if(items2.empty()) return;

		iterator=--items2.end();
		if(iterator->second.change!=changes.end()){
			changes.erase(iterator->second.change);
			iterator->second.change=changes.end();
		}
	};

	auto const constructChange=[&](std::map<int, Item2>::iterator first, std::map<int, Item2>::iterator sec)->Changes::iterator{
		assert(first->first<sec->first);
		if(sec->second.value>first->second.value) return changes.end();
		return changes.emplace(
				first->second.height==sec->second.height ? INT_MAX: (first->second.value-sec->second.value)/(first->second.height-sec->second.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=[&](int rightIndex, Item2 const value){
			assert(value.change==changes.end());
			while(not items2.empty() and 
					items2.rbegin()->second.value-int64_t(numRightColumn-1)*items2.rbegin()->second.height
					>=
					value.value-int64_t(numRightColumn-1)*value.height
				 ){
				popItems2();
			}

			auto const oldSize=items2.size();
			std::map<int, Item2>::iterator iterator=items2.insert(items2.end(), {rightIndex, value});
			assert(items2.size()==oldSize+1);
			if(items2.size()==1) return;

			auto prev=iterator; --prev;
			assert(prev->second.change==changes.end());
			//std::map<int, Item2>::prev tmp=prev;
			prev->second.change=constructChange(prev, iterator);
		};

		auto const maintainItems2=[&]{
			while(not changes.empty()){
				auto const iterator=--changes.end();
				if(iterator->first<numRightColumn-1) break;

				std::map<int, 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->second.change!=changes.end())
					changes.erase(iterator4->second.change);
				iterator4->second.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()->first>=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->second.value-iterator->second.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 lambda function:
meetings.cpp:90:15: warning: unused variable 'oldSize' [-Wunused-variable]
   90 |    auto const oldSize=items2.size();
      |               ^~~~~~~
meetings.cpp: In function 'std::vector<long int> solve(const std::vector<int>&, const std::vector<std::pair<int, int> >&)':
meetings.cpp:164:15: warning: variable 'naiveMinSlopedValue' set but not used [-Wunused-but-set-variable]
  164 |    auto const naiveMinSlopedValue=[&]{
      |               ^~~~~~~~~~~~~~~~~~~

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