Submission #1086857

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086857		Jawad_Akbar_JJ	Strange Device (APIO19_strange_device)	C++17	100 / 100	1014 ms	53292 KiB

strange_device

#include <iostream>
#include <vector>

#include <algorithm>

using namespace std;
#define ll long long
#define i28 __int128

int main(){
	ll n, A, B;
	cin>>n>>A>>B;

	i28 k = A / __gcd(A, B + 1);
	k = k * B;

	vector<pair<ll, ll>> vec;

	for (int i=1;i<=n;i++){
		ll l, r;
		cin>>l>>r;

		if (r - l + 1 >= k){
			cout<<(long long)k<<'\n';
			return 0;
		}
		l = l % k;
		r = r % k;

		if (l <= r)
			vec.push_back({l, r});
		else{
			vec.push_back({l, k - 1});
			vec.push_back({0, r});
		}
	}

	sort(begin(vec), end(vec));

	ll mx = -1, ans = 0;

	for (auto [i, j] : vec){
		mx = max(mx, i - 1);
		ans += max(0LL, j - mx);
		mx = max(mx, j);
	}
	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