#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
int main() {
ios :: sync_with_stdio(0); cin.tie(0);
int n;
long long A, B;
vector <pair <long long, int> > events;
cin >> n >> A >> B;
long long T = A / __gcd(A, B + 1) * B;
for (int i = 0; i < n; ++i) {
int L, R;
cin >> L >> R;
if (R - L + 1 >= T) {
cout << T << '\n';
exit(0);
}
L %= T, R %= T;
if (L <= R) {
events.push_back({L, 1});
events.push_back({R + 1, -1});
} else {
events.push_back({L, 1});
events.push_back({T, -1});
events.push_back({0, 1});
events.push_back({R + 1, -1});
}
}
sort(events.begin(), events.end());
int cur = 0;
long long ans = 0;
for (int i = 0; i + 1 < events.size(); ++i) {
cur += events[i].second;
if (cur != 0) ans += events[i + 1].first - events[i].first;
}
cout << ans;
}
Compilation message
strange_device.cpp: In function 'int main()':
strange_device.cpp:42:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for (int i = 0; i + 1 < events.size(); ++i) {
| ~~~~~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Incorrect |
2 ms |
1492 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
324 KB |
Output is correct |
2 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Incorrect |
237 ms |
66224 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Incorrect |
237 ms |
66224 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Incorrect |
237 ms |
66224 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
316 KB |
Output is correct |
2 |
Incorrect |
23 ms |
8648 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Incorrect |
2 ms |
1492 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |