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>
typedef long long ll;
int main() {
std::ios::sync_with_stdio(0); std::cin.tie(0);
ll n, a, b; std::cin >> n >> a >> b;
ll val = 1LL << 60LL, c = 0;
std::vector <std::pair <ll, ll>> p(n), v;
for (auto& P : p) std::cin >> P.first >> P.second;
int gcd = std::__gcd(a, b + 1);
if ((a / gcd) <= val / b) c = (a / gcd) * b;
for (auto& x : p) {
ll l = x.first, r = x.second;
if (c && r - l + 1LL >= c) {
std::cout << c << "\n";
return 0;
}
if (c) l %= c, r %= c;
if (l <= r) v.push_back({ l, r });
else v.push_back({ 0LL, r }), v.push_back({ l, c - 1LL });
}
ll last = -1, to = 0;
std::sort(v.begin(), v.end());
ll ans = 0;
for (auto& x : v) {
ll l = x.first, r = x.second;
if (last == -1LL) to = r, last = l;
else if (to < l) {
ans += to - last + 1LL;
to = r, last = l;
} else to = std::max(to, r);
}
if (last != -1LL) ans += to - last + 1LL;
std::cout << ans << "\n";
//std::cout.flush(); std::cin >> n;
}
# | 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... |