Submission #299896

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
299896	2020-09-16T00:44:26 Z	user202729	Meetings (IOI18_meetings)	C++17	100 / 100	2759 ms	214908 KB

meetings

// moreflags=grader.cpp
// without transparent comparator.
// a little easier to implement.
#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::set<Item2>::iterator>;
struct Item2{
	int rightIndex;
	int height; // ==height[rightIndex]
	int64_t value;
	mutable Changes::iterator change; // to destroy this element
	bool operator<(Item2 const& other) const{return rightIndex<other.rightIndex;}
};

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

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

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

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

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

			--iterator;
			assert(iterator->change==changes.end());
			//std::set<Item2>::iterator tmp=iterator;
			iterator->change=constructChange(iterator, value);
		};

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

				std::set<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->change!=changes.end())
					changes.erase(iterator4->change);
				iterator4->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()->rightIndex>=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->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

meetings.cpp: In lambda function:
meetings.cpp:92:15: warning: unused variable 'oldSize' [-Wunused-variable]
   92 |    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:166:15: warning: variable 'naiveMinSlopedValue' set but not used [-Wunused-but-set-variable]
  166 |    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	3 ms	640 KB	Output is correct
3	Correct	3 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	3 ms	640 KB	Output is correct
3	Correct	3 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	7 ms	1164 KB	Output is correct
12	Correct	7 ms	1280 KB	Output is correct
13	Correct	7 ms	1168 KB	Output is correct
14	Correct	7 ms	1456 KB	Output is correct
15	Correct	8 ms	1228 KB	Output is correct

Subtask #3

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	416 KB	Output is correct
2	Correct	44 ms	4596 KB	Output is correct
3	Correct	188 ms	26232 KB	Output is correct
4	Correct	150 ms	22632 KB	Output is correct
5	Correct	177 ms	27296 KB	Output is correct
6	Correct	150 ms	27364 KB	Output is correct
7	Correct	177 ms	29088 KB	Output is correct

Subtask #4

24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	416 KB	Output is correct
2	Correct	44 ms	4596 KB	Output is correct
3	Correct	188 ms	26232 KB	Output is correct
4	Correct	150 ms	22632 KB	Output is correct
5	Correct	177 ms	27296 KB	Output is correct
6	Correct	150 ms	27364 KB	Output is correct
7	Correct	177 ms	29088 KB	Output is correct
8	Correct	177 ms	22968 KB	Output is correct
9	Correct	125 ms	22108 KB	Output is correct
10	Correct	167 ms	23984 KB	Output is correct
11	Correct	171 ms	22600 KB	Output is correct
12	Correct	127 ms	21744 KB	Output is correct
13	Correct	165 ms	23624 KB	Output is correct
14	Correct	166 ms	26260 KB	Output is correct
15	Correct	151 ms	22472 KB	Output is correct
16	Correct	158 ms	26188 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	3 ms	640 KB	Output is correct
3	Correct	3 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	7 ms	1164 KB	Output is correct
12	Correct	7 ms	1280 KB	Output is correct
13	Correct	7 ms	1168 KB	Output is correct
14	Correct	7 ms	1456 KB	Output is correct
15	Correct	8 ms	1228 KB	Output is correct
16	Correct	1 ms	416 KB	Output is correct
17	Correct	44 ms	4596 KB	Output is correct
18	Correct	188 ms	26232 KB	Output is correct
19	Correct	150 ms	22632 KB	Output is correct
20	Correct	177 ms	27296 KB	Output is correct
21	Correct	150 ms	27364 KB	Output is correct
22	Correct	177 ms	29088 KB	Output is correct
23	Correct	177 ms	22968 KB	Output is correct
24	Correct	125 ms	22108 KB	Output is correct
25	Correct	167 ms	23984 KB	Output is correct
26	Correct	171 ms	22600 KB	Output is correct
27	Correct	127 ms	21744 KB	Output is correct
28	Correct	165 ms	23624 KB	Output is correct
29	Correct	166 ms	26260 KB	Output is correct
30	Correct	151 ms	22472 KB	Output is correct
31	Correct	158 ms	26188 KB	Output is correct
32	Correct	1752 ms	183220 KB	Output is correct
33	Correct	1002 ms	177276 KB	Output is correct
34	Correct	1861 ms	191912 KB	Output is correct
35	Correct	1756 ms	183348 KB	Output is correct
36	Correct	1030 ms	177604 KB	Output is correct
37	Correct	1869 ms	192136 KB	Output is correct
38	Correct	1950 ms	211560 KB	Output is correct
39	Correct	2759 ms	214908 KB	Output is correct
40	Correct	1918 ms	187756 KB	Output is correct
41	Correct	1693 ms	210444 KB	Output is correct
42	Correct	1892 ms	211236 KB	Output is correct
43	Correct	1872 ms	211372 KB	Output is correct
44	Correct	1827 ms	197272 KB	Output is correct