#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
#define ios ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
using namespace std;
int main() {
ios
int n;
cin >> n;
ll A, B;
cin >> A >> B;
ll S = 0;
map <ll, ll> was;
ll l[n], r[n], ans = 0;
for (int i = 0; i < n; ++ i) {
cin >> l[i] >> r[i];
S += r[i] - l[i] + 1;
}/*
if (A > 1e18 / B + 1) {
cout << S;
return 0;
}*/
ll val = A * B / __gcd(B - 1, A);
vector <pair <ll, ll> > v;
for (int i = 0; i < n; ++ i) {
if (l[i] + val >= r[i]) {
cout << min(S, val);
return 0;
}
ll ml = l[i] % val, mr = r[i] % val;
if (ml <= mr) {
v.push_back({ml, mr});
}
else {
v.push_back({0, ml});
v.push_back({mr, val - 1});
}
}
sort(v.begin(), v.end());
ans = v[0].second - v[0].first + 1;/*
for (int i = 0; i < v.size(); ++ i) {
cout << v[i].first << " " << v[i].second << endl;
}*/
for (int i = 1; i < v.size(); ++ i) {
ll nl = v[i].first, nr = v[i].second;
if (nl > v[i - 1].second) {
ans += nr - nl + 1;
continue;
}
else if (nr <= v[i - 1].second) {
v[i].second = v[i - 1].second;
}
else {
ans += nr - v[i - 1].second;
}
}
cout << ans;
return 0;
}
Compilation message
strange_device.cpp: In function 'int main()':
strange_device.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for (int i = 1; i < v.size(); ++ i) {
| ~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Incorrect |
5 ms |
460 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Incorrect |
388 ms |
15948 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Incorrect |
388 ms |
15948 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Incorrect |
388 ms |
15948 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Incorrect |
43 ms |
5572 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Incorrect |
5 ms |
460 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |