# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
995138 | mrwang | Strange Device (APIO19_strange_device) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 3e18;
ll gcd(ll a, ll b){
return __gcd(a, b);
}
ll get(ll a, ll b){
ll c = (a / gcd(a, b + 1)), hi = inf / b;
if(c > hi){
c = inf;
}
else{
c *= b;
}
return c;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll t = 1;
while(t--){
ll n, a, b, i, l, r;
cin >> n >> a >> b;
ll x = get(a, b);
vector<array<ll, 2>> v;
bool ok = 1;
for(i = 1; i <= n; i++){
cin >> l >> r;
ok &= ((r - l + 1) >= x);
l %= x;
r %= x;
if(r < l){
v.push_back({l, x - 1});
v.push_back({0, r});
}
else{
v.push_back({l, r});
}
}
if(ok){
cout << x << "\n";
return;
}
sort(v.begin(), v.end());
ll s = 0, hi = -1;
for(i = 0; i < v.size(); i++){
if(v[i][0] > hi){
s += (v[i][1] - v[i][0] + 1);
hi = v[i][1];
}
else
{
s+=max(0ll,v[i][1]-hi);
hi=max(hi,v[i][1]);
}
}
cout << s << "\n";
}
}