Submission #1044709

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044709		vjudge1	Strange Device (APIO19_strange_device)	C++17	100 / 100	280 ms	40880 KiB

strange_device

#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
using namespace std;
const int C = inf;

int32_t main(){
	fast
	int n, a, b;
	cin >> n >> a >> b;
	__int128__ g = gcd(a, b + 1);
	__int128__ temp = (__int128__)a / g * b;
	if(temp > C) {
		int sum = 0;
		for(int i = 0; i < n; i++) {
			int l, r;
			cin >> l >> r;
			sum += r - l + 1;
		}
		cout << sum;
		return 0;
	}
	int tekrar = temp;
	vector <pair<int, int> > ranges;
	for(int i = 0; i < n; i++) {
		int l, r;
		cin >> l >> r;
		if(r - l + 1 >= tekrar) {
			cout << tekrar;
			return 0;
		}
		int ll = l % tekrar, rr = r % tekrar;
		if(ll <= rr) {
			ranges.push_back({ll, rr});
		}
		else {
			ranges.push_back({0, rr});
			ranges.push_back({ll, tekrar - 1});
		}
	}
	sort(ranges.begin(), ranges.end());
	int lastr = -inf, ans = 0;
	for(auto [l, r]:ranges) {
		if(l > lastr) {
			ans += r - l + 1;
		}
		else {
			ans += max(0ll, r - lastr);
		}
		lastr = max(lastr, r);
	}
	cout << ans;
}

• 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