oj.uz

Submission #247379

# Submission time Handle Problem Language Result Execution time Memory
247379 2020-07-11T09:38:43 Z user202729 New Home (APIO18_new_home) C++17
33 / 100
 2841 ms 222632 KB 
// sub 4
// optimized


#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(value<=data[node].value) return;
		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:177:41: warning: unused variable 'time' [-Wunused-variable]
   auto const [position, time, data, type]=*iterator;
                                         ^
new_home.cpp:177:41: warning: unused variable 'type' [-Wunused-variable]
new_home.cpp:241:41: warning: unused variable 'time' [-Wunused-variable]
   auto const [position, time, data, type]=*iterator;
                                         ^
new_home.cpp:213:12: warning: 'previous' may be used uninitialized in this function [-Wmaybe-uninitialized]
   up.change(last, maxQueryPosition, -last);
   ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Runtime error 5 ms 256 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Runtime error 5 ms 256 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 518 ms 36476 KB Output is correct
2 Correct 1768 ms 116052 KB Output is correct
3 Correct 417 ms 47608 KB Output is correct
4 Correct 535 ms 38136 KB Output is correct
5 Correct 2379 ms 222632 KB Output is correct
6 Correct 2084 ms 179296 KB Output is correct
7 Correct 342 ms 47508 KB Output is correct
8 Correct 362 ms 38264 KB Output is correct
9 Correct 382 ms 35192 KB Output is correct
10 Correct 551 ms 38100 KB Output is correct
11 Correct 729 ms 72044 KB Output is correct
12 Correct 534 ms 41484 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 786 ms 34204 KB Output is correct
2 Correct 416 ms 31096 KB Output is correct
3 Correct 2080 ms 116348 KB Output is correct
4 Correct 469 ms 45560 KB Output is correct
5 Correct 553 ms 34548 KB Output is correct
6 Correct 522 ms 36344 KB Output is correct
7 Correct 2841 ms 222424 KB Output is correct
8 Correct 2284 ms 179184 KB Output is correct
9 Correct 447 ms 46840 KB Output is correct
10 Correct 482 ms 36320 KB Output is correct
11 Correct 551 ms 34208 KB Output is correct
12 Correct 968 ms 42436 KB Output is correct
13 Correct 901 ms 105416 KB Output is correct
14 Correct 1020 ms 178144 KB Output is correct
15 Correct 852 ms 101596 KB Output is correct
16 Correct 637 ms 41724 KB Output is correct
17 Correct 991 ms 105312 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Runtime error 5 ms 256 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Runtime error 5 ms 256 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -