Submission #248374

#	Time	Username	Problem	Language	Result	Execution time	Memory
248374		user202729	Meetings (IOI18_meetings)	C++17	60 / 100	5575 ms	287608 KiB

meetings

// moreflags=grader.cpp
#include "meetings.h"

#include<functional>
#include<cassert>
#include<vector>
#include<limits>
//#include<algorithm>

template<class T, class Compare=std::less<T>> struct Maximum{
	std::vector<std::vector<T>> data;
	Compare compare;

	Maximum(){}

	template<class F> Maximum(int number, F f, Compare compare_={}){
		reset(number, f, compare_);
	}

	template<class F> void reset(int number, F f, Compare compare_={}){
		data.clear(); compare=std::move(compare_);

		data.emplace_back(number);
		for(int index=0; index<number; ++index)data[0][index]=f(index);
		for(int step=1; step<(int)data.back().size(); step<<=1){
			auto const& a=data.back();
			std::vector<T> b(a.begin(), a.end()-step);
			std::transform(begin(b), end(b), begin(a)+step, b.begin(),[&](auto first, auto sec){
				return std::max(first, sec, compare);
			});
			data.push_back(std::move(b));
		}
	}

	T get(int left, int right)const{
		auto const layer=31^__builtin_clz(right-left);
		return std::max(data[layer][left], data[layer][right-(1<<layer)], compare);
	}
};

struct Tree{
	std::vector<int64_t> data; // fake tree
	void reset(int number){
		data.assign(number, 0);
	}
	void add(int left, int right, int64_t value){
		for(int i=left; i<right; ++i) data[i]+=value;
	}
	void minSegment(int left, int right, int64_t multiplier, int64_t offset){
		// actually this function is the hardest to implement in the real implementation, unless there's some special properties of this problem...
		for(int i=left; i<right; ++i) data[i]=std::min(data[i], multiplier*i+offset);
	}
	/*
	int64_t minimum(int left, int right){
		int64_t result=std::numeric_limits<int64_t>::max();
		for(int i=left; i<right; ++i) result=std::min(result, data[i]);
		return result;
	}
	*/
	int64_t get(int index){return data[index];}
};

struct Query{int left, right, index;}; // inclusive

struct Solve{
	std::vector<int> height, queryLeft, queryRight;

	Maximum<std::pair<int, int>> leftHeight, rightHeight;
	int maxHeightIndex(int left, int right)const{
		// get index with maximum height, or if there's many equal, get the middle most one
		// (middle most is not necessary in the full implementation, if any)
		if(left+1==right) return left;

		int const mid=(left+right)>>1;
		auto const [height1, _index1]=leftHeight.get(mid, right);
		auto const [height2, index2]=rightHeight.get(left, mid);
		auto const index1=-_index1;
		assert(mid-index2>0 and index1-mid>=0);

		if(height1>height2) return index1;
		if(height1<height2) return index2;
		if(mid-index2<index1-mid) return index2; else return index1;
	}

	Tree prefix, suffix;

	std::vector<long long> result;

	void process(int const left, int const right, std::vector<Query>::iterator first, std::vector<Query>::iterator last){
		// left..=right
		assert(left<=right);

		std::for_each(first, last,[&](auto it){
			auto [qleft, qright, _]=it;
			assert(left<=qleft and qleft<=qright and qright<=right);
		});

		if(left==right){
			assert(prefix.get(left)==0);
			assert(suffix.get(left)==0);
			prefix.add(left, left+1, height[left]);
			suffix.add(left, left+1, height[left]);

			std::for_each(first, last,[&](auto it){
				auto [qleft, qright, queryIndex]=it;
				assert(left==qleft and left==qright);
				result[queryIndex]=height[left];
			});

			return;
		}

		auto const mid=maxHeightIndex(left, right+1);
		assert(left<=mid); assert(mid<=right);
		{
			auto const iterator=std::partition(first, last, [&](auto it){return it.right<mid;});
			if(left<mid)
				process(left, mid-1, first, iterator);
			else assert(first==iterator);
			first=iterator;
		}
		{
			auto const iterator=std::partition(first, last, [&](auto it){return it.left>mid;});
			if(mid<right)
				process(mid+1, right, first, iterator);
			else assert(first==iterator);
			first=iterator;
		}

		assert(prefix.get(mid)==0); assert(suffix.get(mid)==0);
		auto const heightMid=height[mid];

		std::for_each(first, last,[&](auto it){
			auto [qleft, qright, queryIndex]=it;
			assert(left<=qleft and qleft<=mid and mid<=qright and qright<=right);
			result[queryIndex]=std::min(
					suffix.get(qleft)+int64_t(qright-mid+1)*heightMid,
					prefix.get(qright)+int64_t(mid-qleft+1)*heightMid);
		});

		assert(prefix.get(mid)==0);
		prefix.add(mid, right+1, int64_t(mid-left+1)*heightMid);
		prefix.minSegment(mid, right+1, heightMid, (mid==left ? 0: prefix.get(mid-1))
				-int64_t(mid-1)*heightMid);

		assert(suffix.get(mid)==0);
		suffix.add(left, mid+1, int64_t(right-mid+1)*heightMid);
		suffix.minSegment(left, mid+1, -heightMid, (mid==right ? 0: suffix.get(mid+1))
				+int64_t(mid+1)*heightMid);

		assert(prefix.get(right)==suffix.get(left));
	}

	std::vector<long long> solve() {
		leftHeight.reset((int)height.size(), [&](auto index){ return std::pair(height[index], -index); });
		rightHeight.reset((int)height.size(), [&](auto index){ return std::pair(height[index], index); });
		prefix.reset((int)height.size());
		suffix.reset((int)height.size());

		std::vector<Query> queries(queryLeft.size());
		for(int index=0; index<(int)queries.size(); ++index)
			queries[index]={queryLeft[index], queryRight[index], index};

		result.resize(queries.size());
		process(0, (int)height.size()-1, begin(queries), end(queries));
		return result;
	}
};

std::vector<long long> minimum_costs(std::vector<int> height, std::vector<int> left, std::vector<int> right) {
	return Solve{std::move(height), std::move(left), std::move(right)}.solve();
}

Compilation message (stderr)

meetings.cpp: In instantiation of 'Solve::process(int, int, std::vector<Query>::iterator, std::vector<Query>::iterator)::<lambda(auto:3)> [with auto:3 = Query]':
/usr/include/c++/7/bits/stl_algo.h:3884:5:   required from '_Funct std::for_each(_IIter, _IIter, _Funct) [with _IIter = __gnu_cxx::__normal_iterator<Query*, std::vector<Query> >; _Funct = Solve::process(int, int, std::vector<Query>::iterator, std::vector<Query>::iterator)::<lambda(auto:3)>]'
meetings.cpp:96:4:   required from here
meetings.cpp:94:26: warning: unused variable '_' [-Wunused-variable]
    auto [qleft, qright, _]=it;
                          ^

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