Submission #1032628

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032628		Muhammet	Strange Device (APIO19_strange_device)	C++17	100 / 100	345 ms	69828 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;

#define ll long long int
#define sz(x) (int)x.size()
#define ff first
#define ss second

const ll N = 1000005;
const ll M = 1e18;

ll T, n, a, b, l[N], r[N];

int main(){
	ios::sync_with_stdio(false); cin.tie(0);

	cin >> n >> a >> b;
	ll x = 0;
	for(int i = 1; i <= n; i++){
		cin >> l[i] >> r[i];
		x += (r[i]-l[i]+1);
	}
	ll m = __gcd(a,b+1);
	m = (a/m);
	ll k = 0;
	if(M/b < m) {
		cout << x;
		return 0;
	}
	k = m*b;
	vector <pair<ll,ll>> v;
	for(int i = 1; i <= n; i++){
		if(r[i]-l[i]+1 >= k){
			cout << k;
			return 0;
		}
		ll c = (l[i]%k), d = r[i]%k;
		if(c > d){
			v.push_back({c,k-1});
			v.push_back({0,d});
		}
		else {
			v.push_back({c,d});
		}
	}
	sort(v.begin(), v.end());
	ll mn = v[0].ff, mx = v[0].ss, ans = 0;
	for(auto i : v){
		if(i.ff > mx){
			ans += (mx-mn+1);
			mn = 1e18;
			mx = -1e18;
		}
		mn = min(i.ff,mn);
		mx = max(mx,i.ss);
	}
	if(mn <= mx){
		ans += (mx-mn+1);
	}
	
	cout << ans;

	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