Submission #247377

# Submission time Handle Problem Language Result Execution time Memory
247377 2020-07-11T09:30:41 Z user202729 New Home (APIO18_new_home) C++17
33 / 100
3399 ms 238552 KB
// sub 4


#ifndef LOCAL
#define NDEBUG 1
#include<cassert>
#include<cstdio>
#include<vector>
#include<cstdint>
#include<climits>
#include<array>
#include<algorithm>
#include<set>
struct Input{
	int get(){return std::getchar();}

	/*
	auto& operator>>(std::string& it){
		it.clear();
		char ch;
		do{
			while((ch=(char)get())>' ') it+=ch;
		}while(it.empty());
		return *this;
	}
	*/

	auto& ignore(std::size_t number){
		while(number--) get();
		return *this;
	}

	auto& operator>>(char& it){
		while((it=(char)get())<=' ') {}
		return *this;
	}

	template<class T, class=std::enable_if<std::is_integral<T>::value>>
	auto& operator>>(T& it){
		while((it=get())<'0') {}
		it-='0';
		int ch; while((ch=get())>='0') it=it*10+ch-'0';
		return *this;
	}
} cin;
struct Output{
	auto& operator<<(char it) {
		std::putchar(it); return *this;
	}
	auto& operator<<(int it) {
		std::printf("%d", it); return *this;
	}
	auto& operator<<(char const* it) {
		for(; *it; ++it) std::putchar(*it);
		return *this;
	}
} cout;

#else
#include "/tmp/all.h"
#endif

// remark about precompiled headers and compile time: #include<string> or #include<iostream> adds about 0.5s to the compilation time, even with precompiled header.
// ...
// 
// libraries are either too long (some sites allow less than Codeforces...) or not having enough functionality.
// A problem with competitive programming and single-file solution...

int constexpr maxQueryPosition=
#ifdef LOCAL
	//10
	100000001
#else
	100000001
#endif
	;

struct Tree{
	struct Node{
		int left, right; // 0: not yet created
		int value;
	};
	std::vector<Node> data;
	Tree(): data(1, {0, 0, INT_MIN}){}

	int get(int index,
			int node=0, int left=0, int right=maxQueryPosition, int result=INT_MIN){
		int const mid=(left+right)>>1;
		assert(left<=index); assert(index<right);
		result=std::max(result, data[node].value);

		if(index<mid){
			if(auto const child=data[node].left) return get(index, child, left, mid, result);
		}else{
			if(auto const child=data[node].right) return get(index, child, mid, right, result);
		}
		return result;
	}
	void change(int changeLeft, int changeRight, int value,
			int node=0, int left=0, int right=maxQueryPosition){
		assert(changeRight<=maxQueryPosition);

		assert(not(changeLeft>=right or changeRight<=left));
		if(changeLeft<=left and right<=changeRight){
			data[node].value=std::max(data[node].value, value);
			return;
		}

		int const mid=(left+right)>>1;
		if(changeLeft<mid){
			auto& child=data[node].left;
			int child1=child; // data.push_back invalidates child
			if(child==0){child=child1=(int)data.size(); data.push_back({0, 0, INT_MIN});}
			change(changeLeft, changeRight, value, child1, left, mid);
		}
		if(changeRight>mid){
			auto& child=data[node].right;
			int child1=child;
			if(child==0){child=child1=(int)data.size(); data.push_back({0, 0, INT_MIN});}
			change(changeLeft, changeRight, value, child1, mid, right);
		}
	}
};

int main(){
	/*
	{
		Tree tree;
		tree.change(2, 5, 4);
		cout<<tree.get(2)<<'\n';
		return 0;
	}
	*/

	int numStore, numType, numQuery; cin>>numStore>>numType>>numQuery;
	struct Event{
		int position, time;
		int data; // shopType or queryIndex
		enum class Type{
			open, close, query
		};
		Type type;

		bool operator<(Event it)const{
			//check(); it.check();

			return time!=it.time ? time<it.time: type<it.type;
		} // query after open/close if same time

	};

	std::vector<Event> events; events.reserve(numStore*2+numQuery);

	for(int _=0; _<numStore; ++_){
		int position, type, open, close; cin>>position>>type>>open>>close;
		assert(1<=type and type<=numType); --type;
		if(open!=1) return 1;
		events.push_back({position, open, type, Event::Type::open});
		events.push_back({position, close+1, type, Event::Type::close});
	}


	for(int queryIndex=0; queryIndex<numQuery; ++queryIndex){
		int position, time; cin>>position>>time;
		assert(0<=position); assert(position<maxQueryPosition);
		events.push_back({position, time, queryIndex, Event::Type::query});
	}
	std::sort(begin(events), end(events));

	// a map<int, int> would work too
	std::vector<std::multiset<int>> positions(numType);

	auto iterator=events.begin();
	while(iterator!=events.end() and iterator->type==Event::Type::open){
		auto const [position, time, data, type]=*iterator;
		++iterator;
		assert(type==Event::Type::open);
		positions[data].insert(position);
	}

	/*
	struct Tree{
		std::vector<int> data;
		Tree(): data(maxQueryPosition, INT_MIN){}
		int get(int index){
			return data[index];
		}
		void change(int left, int right, int value){
			for(int i=left; i<right; ++i) data[i]=std::max(data[i], value);
		}
	};
	*/

	Tree up, down;
	bool possible=true;

	auto const getResult=[&](int position){
		if(not possible) return -1;
		return std::max(up.get(position)+position*2, down.get(position))-position; // avoid integer overflow
	};

	auto const changeSegment=[&](int last, int position){
		auto const mid=(last+position+1)/2;
		up.change(last, mid, -last);
		down.change(mid, position, position);
	};
	auto const changePrefix=[&](int position){
		down.change(0, position, position);
	};
	auto const changeSuffix=[&](int last){
		up.change(last, maxQueryPosition, -last);
	};

	for(auto const& it: positions){
		if(it.empty()){ possible=false; break; }

		int last=-1;
		for(auto position: it){
			if(position==last) continue;
			if(last<0){
				assert(last==-1);

				// [..position]
				changePrefix(position);
			}else{
				// [last..position]
				changeSegment(last, position);
			}
			last=position;
		}
		// [last..]
		changeSuffix(last);
	}


	std::vector<int> result(numQuery);

	for(; iterator!=events.end();++iterator){
		auto const [position, time, data, type]=*iterator;
		switch(type){
			case Event::Type::open:
				assert(false); __builtin_unreachable();
			case Event::Type::close:
				{
					auto const shopType=data;
					auto const nextIterator=positions[shopType].erase(positions[shopType].find(position));
					bool const havePrevious=nextIterator!=positions[shopType].begin();
					bool const haveNext=nextIterator!=positions[shopType].end();

					int previous; if(havePrevious) previous=*std::prev(nextIterator);
					int next; if(haveNext) next=*nextIterator;
					if((havePrevious and previous==position) or (haveNext and next==position))
						break; // nothing changes.

					if(havePrevious and haveNext){
						changeSegment(previous, next);
					}else if(havePrevious){
						changeSuffix(previous);
					}else if(haveNext){
						changePrefix(next);
					}else{
						possible=false;
					}
				}
				break;
			case Event::Type::query:
				result[data]=getResult(position);
				break;
		}
	}

	for(auto it: result) cout<<it<<'\n';
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:175:41: warning: unused variable 'time' [-Wunused-variable]
   auto const [position, time, data, type]=*iterator;
                                         ^
new_home.cpp:175:41: warning: unused variable 'type' [-Wunused-variable]
new_home.cpp:239:41: warning: unused variable 'time' [-Wunused-variable]
   auto const [position, time, data, type]=*iterator;
                                         ^
new_home.cpp:211:12: warning: 'previous' may be used uninitialized in this function [-Wmaybe-uninitialized]
   up.change(last, maxQueryPosition, -last);
   ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Runtime error 4 ms 256 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Runtime error 4 ms 256 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2652 ms 183292 KB Output is correct
2 Correct 2736 ms 225004 KB Output is correct
3 Correct 1280 ms 140784 KB Output is correct
4 Correct 2377 ms 195208 KB Output is correct
5 Correct 2338 ms 234176 KB Output is correct
6 Correct 2576 ms 237520 KB Output is correct
7 Correct 1265 ms 140700 KB Output is correct
8 Correct 2021 ms 195432 KB Output is correct
9 Correct 2646 ms 211744 KB Output is correct
10 Correct 3010 ms 238552 KB Output is correct
11 Correct 1614 ms 233724 KB Output is correct
12 Correct 2032 ms 236356 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3399 ms 217536 KB Output is correct
2 Correct 402 ms 30320 KB Output is correct
3 Correct 2914 ms 237784 KB Output is correct
4 Correct 1033 ms 138620 KB Output is correct
5 Correct 2255 ms 194680 KB Output is correct
6 Correct 2008 ms 194700 KB Output is correct
7 Correct 2570 ms 234016 KB Output is correct
8 Correct 2764 ms 237308 KB Output is correct
9 Correct 1232 ms 139840 KB Output is correct
10 Correct 2348 ms 193600 KB Output is correct
11 Correct 3212 ms 222136 KB Output is correct
12 Correct 3339 ms 238228 KB Output is correct
13 Correct 1341 ms 224140 KB Output is correct
14 Correct 1278 ms 224000 KB Output is correct
15 Correct 1540 ms 231736 KB Output is correct
16 Correct 2086 ms 232528 KB Output is correct
17 Correct 1573 ms 231728 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Runtime error 4 ms 256 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Runtime error 4 ms 256 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -