Submission #519315

#	Time	Username	Problem	Language	Result	Execution time	Memory
519315		tibinyte	Strange Device (APIO19_strange_device)	C++14	0 / 100	30 ms	332 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;
bool will_overflow(long long a, long long b) {
	long long c = a * b;
	if (a != c / b) {
		return true;
	}
	return false;
}
long long gcd(long long a, long long b) {
	while (b) {
		long long c = a % b;
		a = b;
		b = c;
	}
	return a;
}
int main() {
	cin.tie(nullptr)->ios_base::sync_with_stdio(false);
	long long n, a, b;
	cin >> n >> a >> b;
	long long p = 0;
	if (will_overflow(a / gcd(a, b + 1), b)) {
		p = 1e18 + 1;
	}
	else {
		p = a / gcd(a, b + 1) * b;
	}
	map<int, int> wh;
	auto update = [&](int st, int dr) {
		wh[st]++;
		wh[dr + 1]--;
	};
	for (int i = 1; i <= n; ++i) {
		int st, dr;
		cin >> st >> dr;
		int lg = (dr - st) + 1;
		st %= p;
		if (st + lg - 1 < p) {
			update(st, st + lg - 1);
		}
		else {
			update(st, p - 1);
			lg -= (p - st);
			st = 0;
			if (st + lg - 1 < p) {
				update(st, st + lg - 1);
			}
			else {
				cout << p << '\n';
				return 0;
			}
		}
	}
	long long ans = 0;
	long long s = 0;
	for (map<int, int>::iterator i = wh.begin(); i != prev(wh.end()); ++i) {
		s += i->second;
		int st = i->first, dr = next(i)->first - 1;
		if (s) {
			ans += dr - st + 1;
		}
	}
	cout << ans;
}

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