Submission #641079

#	Time	Username	Problem	Language	Result	Execution time	Memory
641079		ymm	Strange Device (APIO19_strange_device)	C++17	15 / 100	1284 ms	332 KiB

strange_device

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

set<pll> s;

void add(ll l, ll r)
{
	auto it = s.lower_bound(pll{l, -1});
	if (it != s.begin()) {
		--it;
		if (it->second >= l) {
			l = it->first;
			s.erase(it++);
		} else {
			++it;
		}
	}
	while (it != s.end() && r >= it->first) {
		r = max(r, it->second);
		s.erase(it++);
	}
	s.insert({l, r});
}

int main()
{
	ll n, A, B;
	cin >> n >> A >> B;
	__int128 p = (__int128)A * B / __gcd(A, B+1);
	if (p < LONG_LONG_MAX)
		p = p * B / __gcd((ll)p, B);
	Loop (i,0,n) {
		ll l, r;
		cin >> l >> r;
		if (r - l + 1 >= p) {
			l = 0;
			r = p;
		} else {
			l %= p;
			r %= p;
			++r;
		}
		if (l < r) {
			add(l, r);
		} else {
			add(l, p);
			add(0, r);
		}
	}
	ll ans = 0;
	for (auto [x, y] : s)
		ans += y - x;
	cout << ans << '\n';
}

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