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>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
using namespace std;
const int C = inf;
int32_t main(){
fast
int n, a, b;
cin >> n >> a >> b;
__int128__ g = gcd(a, b + 1);
__int128__ temp = (__int128__)a / g * b;
if(temp > C) {
int sum = 0;
for(int i = 0; i < n; i++) {
int l, r;
cin >> l >> r;
sum += r - l + 1;
}
cout << sum;
return 0;
}
int tekrar = temp;
vector <pair<int, int> > ranges;
for(int i = 0; i < n; i++) {
int l, r;
cin >> l >> r;
if(r - l + 1 >= tekrar) {
cout << tekrar;
return 0;
}
int ll = l % tekrar, rr = r % tekrar;
if(ll <= rr) {
ranges.push_back({ll, rr});
}
else {
ranges.push_back({0, rr});
ranges.push_back({ll, tekrar - 1});
}
}
sort(ranges.begin(), ranges.end());
int lastr = -inf, ans = 0;
for(auto [l, r]:ranges) {
if(l > lastr) {
ans += r - l + 1;
}
else {
ans += max(0ll, r - lastr);
}
lastr = max(lastr, r);
}
cout << ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |