제출 #247378

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
247378		user202729	다리 (APIO19_bridges)	C++17	0 / 100	5 ms	512 KiB

bridges

// 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';
}

컴파일 시 표준 에러 (stderr) 메시지

bridges.cpp: In function 'int main()':
bridges.cpp:177:41: warning: unused variable 'time' [-Wunused-variable]
   auto const [position, time, data, type]=*iterator;
                                         ^
bridges.cpp:177:41: warning: unused variable 'type' [-Wunused-variable]
bridges.cpp:241:41: warning: unused variable 'time' [-Wunused-variable]
   auto const [position, time, data, type]=*iterator;
                                         ^
bridges.cpp:213:12: warning: 'previous' may be used uninitialized in this function [-Wmaybe-uninitialized]
   up.change(last, maxQueryPosition, -last);
   ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27