Submission #246143

#	Time	Username	Problem	Language	Result	Execution time	Memory
246143		user202729	Strange Device (APIO19_strange_device)	C++17	100 / 100	843 ms	28532 KiB

strange_device

//oj.uz/problem/view/APIO19_strange_device
//already.

#ifndef LOCAL
#define NDEBUG 1
#endif
#include<bits/stdc++.h>

int main(){
	std::ios::sync_with_stdio(0);std::cin.tie(0);
	int number; int64_t a, b;
	std::cin>>number>>a>>b;
	auto const c=a/std::gcd(a, b+1);
	int64_t const period=(double)b*(double)c>2e18 ? INT64_MAX: b*c;

	struct Event{
		bool open: 1;
		uint64_t position: 63;

		uint64_t key() const{
			uint64_t result=position<<1|open;
			assert(result==*(uint64_t*) this);
			return result;

			//return position;
		}
		bool operator<(Event it) const{
			return key()<it.key();
		}
	};
	std::vector<Event> events; events.reserve(number*4);

	auto const addSegment=[&](int64_t first, int64_t sec){
		assert(first<sec);
		events.push_back({true, (((uint64_t)1<<63)-1)&first});
		events.push_back({false, (((uint64_t)1<<63)-1)&sec});
	};
	for(int _=0; _<number; ++_){
		int64_t first, sec; std::cin>>first>>sec;
		++sec;
		if(sec-first>=period){
			std::cout<<period<<'\n';
			return 0;
		}
		first%=period; sec%=period;
		if(first<sec){
			addSegment(first, sec);
		}else{
			assert(first!=sec);
			addSegment(first, period);
			if(sec) addSegment(0, sec);
		}
	}

	std::sort(begin(events), end(events));
	int64_t result{};
	int degree{};
	for(auto [open, position]: events){
		if(open){
			if(degree==0) result-=position;
			++degree;
		}else{
			--degree;
			if(degree==0) result+=position;
			//assert(degree>=0);
			//actually this is not guaranteed because of how stuff are sorted...
		}
	}
	std::cout<<result<<'\n';


}

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20
• Subtask 8: 30 / 30