Submission #299897

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
299897	2020-09-16T00:58:41 Z	user202729	Meetings (IOI18_meetings)	C++17	100 / 100	2751 ms	220612 KB

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

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.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	256 KB	Output is correct
2	Correct	2 ms	640 KB	Output is correct
3	Correct	2 ms	640 KB	Output is correct
4	Correct	2 ms	640 KB	Output is correct
5	Correct	3 ms	640 KB	Output is correct
6	Correct	3 ms	768 KB	Output is correct
7	Correct	2 ms	640 KB	Output is correct
8	Correct	2 ms	768 KB	Output is correct
9	Correct	2 ms	768 KB	Output is correct

Subtask #2

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	256 KB	Output is correct
2	Correct	2 ms	640 KB	Output is correct
3	Correct	2 ms	640 KB	Output is correct
4	Correct	2 ms	640 KB	Output is correct
5	Correct	3 ms	640 KB	Output is correct
6	Correct	3 ms	768 KB	Output is correct
7	Correct	2 ms	640 KB	Output is correct
8	Correct	2 ms	768 KB	Output is correct
9	Correct	2 ms	768 KB	Output is correct
10	Correct	7 ms	1280 KB	Output is correct
11	Correct	6 ms	1152 KB	Output is correct
12	Correct	8 ms	1280 KB	Output is correct
13	Correct	7 ms	1296 KB	Output is correct
14	Correct	7 ms	1456 KB	Output is correct
15	Correct	7 ms	1280 KB	Output is correct

Subtask #3

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	40 ms	4584 KB	Output is correct
3	Correct	179 ms	26132 KB	Output is correct
4	Correct	157 ms	22592 KB	Output is correct
5	Correct	157 ms	27284 KB	Output is correct
6	Correct	150 ms	27352 KB	Output is correct
7	Correct	157 ms	29060 KB	Output is correct

Subtask #4

24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	40 ms	4584 KB	Output is correct
3	Correct	179 ms	26132 KB	Output is correct
4	Correct	157 ms	22592 KB	Output is correct
5	Correct	157 ms	27284 KB	Output is correct
6	Correct	150 ms	27352 KB	Output is correct
7	Correct	157 ms	29060 KB	Output is correct
8	Correct	167 ms	22820 KB	Output is correct
9	Correct	127 ms	22108 KB	Output is correct
10	Correct	167 ms	24112 KB	Output is correct
11	Correct	164 ms	22472 KB	Output is correct
12	Correct	126 ms	21744 KB	Output is correct
13	Correct	160 ms	23624 KB	Output is correct
14	Correct	163 ms	26256 KB	Output is correct
15	Correct	154 ms	22472 KB	Output is correct
16	Correct	157 ms	26180 KB	Output is correct

Subtask #5

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	256 KB	Output is correct
2	Correct	2 ms	640 KB	Output is correct
3	Correct	2 ms	640 KB	Output is correct
4	Correct	2 ms	640 KB	Output is correct
5	Correct	3 ms	640 KB	Output is correct
6	Correct	3 ms	768 KB	Output is correct
7	Correct	2 ms	640 KB	Output is correct
8	Correct	2 ms	768 KB	Output is correct
9	Correct	2 ms	768 KB	Output is correct
10	Correct	7 ms	1280 KB	Output is correct
11	Correct	6 ms	1152 KB	Output is correct
12	Correct	8 ms	1280 KB	Output is correct
13	Correct	7 ms	1296 KB	Output is correct
14	Correct	7 ms	1456 KB	Output is correct
15	Correct	7 ms	1280 KB	Output is correct
16	Correct	1 ms	384 KB	Output is correct
17	Correct	40 ms	4584 KB	Output is correct
18	Correct	179 ms	26132 KB	Output is correct
19	Correct	157 ms	22592 KB	Output is correct
20	Correct	157 ms	27284 KB	Output is correct
21	Correct	150 ms	27352 KB	Output is correct
22	Correct	157 ms	29060 KB	Output is correct
23	Correct	167 ms	22820 KB	Output is correct
24	Correct	127 ms	22108 KB	Output is correct
25	Correct	167 ms	24112 KB	Output is correct
26	Correct	164 ms	22472 KB	Output is correct
27	Correct	126 ms	21744 KB	Output is correct
28	Correct	160 ms	23624 KB	Output is correct
29	Correct	163 ms	26256 KB	Output is correct
30	Correct	154 ms	22472 KB	Output is correct
31	Correct	157 ms	26180 KB	Output is correct
32	Correct	1678 ms	183316 KB	Output is correct
33	Correct	1008 ms	177144 KB	Output is correct
34	Correct	1860 ms	192024 KB	Output is correct
35	Correct	1732 ms	183204 KB	Output is correct
36	Correct	1018 ms	177620 KB	Output is correct
37	Correct	1894 ms	191840 KB	Output is correct
38	Correct	1939 ms	211396 KB	Output is correct
39	Correct	2751 ms	220612 KB	Output is correct
40	Correct	1917 ms	188212 KB	Output is correct
41	Correct	1714 ms	210468 KB	Output is correct
42	Correct	1872 ms	211400 KB	Output is correct
43	Correct	1906 ms	211240 KB	Output is correct
44	Correct	1816 ms	197420 KB	Output is correct