Submission #560987

#	Time	Username	Problem	Language	Result	Execution time	Memory
560987		hollwo_pelw	Strange Device (APIO19_strange_device)	C++17	100 / 100	518 ms	41272 KiB

strange_device

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_cxx;
// using namespace __gnu_pbds;

void Hollwo_Pelw();

signed main(){
#ifndef hollwo_pelw_local
	if (fopen(".inp", "r"))
		assert(freopen(".inp", "r", stdin)), assert(freopen(".out", "w", stdout));
#else
	auto start = chrono::steady_clock::now();
#endif
	cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
	int testcases = 1;
	// cin >> testcases;
	for (int test = 1; test <= testcases; test++){
		// cout << "Case #" << test << ": ";
		Hollwo_Pelw();
	}
#ifdef hollwo_pelw_local
	auto end = chrono::steady_clock::now();
	cout << "\nExcution time : " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif
}

/*
t = z * b + y
0 <= y < b
x = (z * (b + 1) + y) % a

y1 == y2
((z1 - z2) * (b + 1)) % a == 0

b = 1e18
b >= 1e12 -> z <= 1e6

*/

#define int long long
const int N = 1e6 + 5, inf = (int) 1e18 + 7;

int n, a, b, l[N], r[N];

void Hollwo_Pelw(){
	cin >> n >> a >> b;
	int f = a / __gcd(a, b + 1), p = inf / f >= b ? f * b : inf;

	vector<pair<int, int>> v;

	for (int i = 1, l, r; i <= n; i++) {
		cin >> l >> r;
		
		if (r - l + 1 >= p)
			return cout << p, (void) 0;

		l %= p, r %= p;
		if (l > r) {
			v.emplace_back(l, p - 1);
			v.emplace_back(0, r);
		} else {
			v.emplace_back(l, r);
		}
	}

	sort(v.begin(), v.end());
	
	int res = 0, curl = 0, curr = -1;
	for (auto [l, r] : v) {
		if (curl > r || l > curr) {
			res += curr - curl + 1;
			curl = l, curr = r;
		}
		curl = min(curl, l), curr = max(curr, r);
	}

	res += curr - curl + 1;

	cout << res << '\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