Submission #244020

#	Time	Username	Problem	Language	Result	Execution time	Memory
244020		hanagasumi	Strange Device (APIO19_strange_device)	C++17	100 / 100	739 ms	17836 KiB

strange_device

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <deque>
#include <map>
#include <set>
#include <complex>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <chrono>
#include <ctime>
 
#define ft first
#define sc second
#define pb push_back
#define len(v) (int)v.size()
#define int ll


using namespace std;
typedef long long ll;
typedef long double ld;
typedef __int128 bigint;
mt19937 rnd(chrono::steady_clock().now().time_since_epoch().count());

bigint gcd(bigint a, bigint b) {
	if(a == 0 || b == 0) 
		return a + b;
	return gcd(b, a % b);
}

signed main() {
	#ifdef PC
		freopen("in.txt", "r", stdin);
		freopen("out.txt", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);	


	int n, a, b, ans = 0;
	cin >> n >> a >> b;
	bigint a1 = a, b1 = b;
	bigint k = ((b1 + 1) * a1 / gcd(b1 + 1, a1)) / (b1 + 1) * b1;
	// cout << k << endl;
	// for (int t = 0; t <= 10; t++) {
	// 	cout << "T " << t << "  " << (t + (t / b)) % a << " " << t % b << endl;
	// }

	
	vector<pair<int, int>> have;
	for (int i = 0; i < n; i++) {
		int l, r;
		cin >> l >> r;
		if(r - l >= k) {
			have.pb({0, k - 1});
			continue;
		}
		int p1 = l % k, p2 = r % k;
		if(p2 >= p1) {
			have.pb({p1, p2});
		}
		else {
			have.pb({p1, k - 1});
			have.pb({0, p2});
		}
	}
	sort(have.begin(), have.end());
	int l = have[0].ft, r = have[0].sc;
	for (int i = 1; i < len(have); i++) {
		if(have[i].ft <= r) {
			r = max(r, have[i].sc);
			continue;
		}
		else {
			ans += (r - l + 1);
			l = have[i].ft, r = have[i].sc;
		}
	}
	ans += (r - l + 1);
	cout << ans << '\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