Submission #258915

#	Time	Username	Problem	Language	Result	Execution time	Memory
258915		parsa_mobed	Strange Device (APIO19_strange_device)	C++14	100 / 100	2359 ms	18968 KiB

strange_device

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair <int , int>
#define F first
#define S second
const int N = 1e6 + 5, inf = 1e18 + 10;
vector <pii> seg;

int32_t main() {
	int n, A, B, ans = 0; cin >> n >> A >> B;
	A = A / __gcd(A, B + 1);
	int AB = A*B;
	if (inf/(long double)A <= B) {
		for (int i = 0,l,r; i < n; i++) cin >> l >> r, ans += r - l + 1;
		cout << ans << "\n";
		return 0;
	}
	for (int i = 0; i < n; i++) {
		int l, r; cin >> l >> r;
		int L = l + (l % AB ? AB - l % AB : 0);
		if (L + AB <= r + 1) return cout << AB << "\n", 0;
		if (l/AB == r/AB) seg.push_back({l % AB, r % AB});
		else seg.push_back({l % AB, AB - 1}), seg.push_back({0, r % AB}); 
	}
	sort(seg.begin(), seg.end());
	int cl = seg[0].F, cr = seg[0].S;
	for (pii p : seg) {
		int l = p.F, r = p.S;
		if (l <= cr) cr = max(cr, r);
		else ans += cr - cl + 1, cl = l, cr = r;
	}
	cout << ans + cr - cl + 1 << "\n";

	return 0;
}

• 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