#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pl;
const int N = 1'000'000;
ll n, a, b, l[N + 10], r[N + 10];
set<pair<pl, pl>> s;
vector<pair<pl, pl>> vec;
ll gcd(ll a, ll b) {
return b? gcd(b, a % b): a;
}
void readInput() {
cin >> n >> a >> b;
for (int i = 1; i <= n; i++)
cin >> l[i] >> r[i];
a /= gcd(a, b + 1);
}
void addSeg(pl l, pl r) {
//cout << l.first << ' ' << l.second << " | " << r.first << ' ' << r.second << endl;
vec.push_back({l, r});
}
void addS(pl l, pl r) {
while (true) {
auto au = s.lower_bound({l, {0ll, 0ll}});
if (au != s.end() && au -> first <= r) {
r = max(r, au -> second);
s.erase(au);
}
else {
s.insert({l, r});
break;
}
}
}
void addAll() {
sort(vec.begin(), vec.end());
reverse(vec.begin(), vec.end());
for (auto [l, r]: vec)
addS(l, r);
}
pl getP(ll x) {
ll q = x / b;
ll r = x % b;
return {((b + 1) % a == 0? 0: q % a), r};
}
ll getLen(pl x, pl y) {
ll lenX = y.first - x.first;
return lenX * b - x.second + y.second + 1;
}
void calcS() {
pl mxP = ((b + 1) % a? make_pair(a - 1, b - 1): make_pair(0ll, b - 1));
for (int i = 1; i <= n; i++) {
ll len = r[i] - l[i] + 1;
if (len / b >= a || ((b + 1) % a == 0 && len >= b)) {
s.insert({{0ll, 0ll}, mxP});
return;
}
}
for (int i = 1; i <= n; i++) {
pl f = getP(l[i]);
pl g = getP(r[i]);
if (g < f) {
addSeg({0ll, 0ll}, g);
addSeg(f, mxP);
}
else
addSeg(f, g);
}
addAll();
}
void calcAnswer() {
ll ans = 0;
while (s.size()) {
ans += getLen(s.begin() -> first, s.begin() -> second);
s.erase(s.begin());
}
cout << ans << flush;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
readInput();
calcS();
calcAnswer();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
2392 KB |
Output is correct |
2 |
Correct |
5 ms |
4060 KB |
Output is correct |
3 |
Correct |
5 ms |
4064 KB |
Output is correct |
4 |
Correct |
0 ms |
2396 KB |
Output is correct |
5 |
Correct |
1 ms |
2480 KB |
Output is correct |
6 |
Correct |
0 ms |
2396 KB |
Output is correct |
7 |
Correct |
0 ms |
2652 KB |
Output is correct |
8 |
Correct |
1 ms |
2396 KB |
Output is correct |
9 |
Correct |
1 ms |
2396 KB |
Output is correct |
10 |
Correct |
0 ms |
2396 KB |
Output is correct |
11 |
Correct |
0 ms |
2396 KB |
Output is correct |
12 |
Incorrect |
0 ms |
2396 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
0 ms |
2396 KB |
Output is correct |
3 |
Correct |
0 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
2396 KB |
Output is correct |
5 |
Correct |
0 ms |
2396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Correct |
1 ms |
2652 KB |
Output is correct |
4 |
Correct |
1 ms |
2396 KB |
Output is correct |
5 |
Correct |
231 ms |
74688 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
2392 KB |
Output is correct |
2 |
Correct |
541 ms |
163624 KB |
Output is correct |
3 |
Correct |
569 ms |
163492 KB |
Output is correct |
4 |
Correct |
557 ms |
164256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
2392 KB |
Output is correct |
2 |
Correct |
541 ms |
163624 KB |
Output is correct |
3 |
Correct |
569 ms |
163492 KB |
Output is correct |
4 |
Correct |
557 ms |
164256 KB |
Output is correct |
5 |
Correct |
0 ms |
2396 KB |
Output is correct |
6 |
Correct |
555 ms |
163512 KB |
Output is correct |
7 |
Correct |
553 ms |
163236 KB |
Output is correct |
8 |
Correct |
568 ms |
164012 KB |
Output is correct |
9 |
Correct |
621 ms |
164008 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
2392 KB |
Output is correct |
2 |
Correct |
541 ms |
163624 KB |
Output is correct |
3 |
Correct |
569 ms |
163492 KB |
Output is correct |
4 |
Correct |
557 ms |
164256 KB |
Output is correct |
5 |
Correct |
1 ms |
2396 KB |
Output is correct |
6 |
Correct |
50 ms |
21624 KB |
Output is correct |
7 |
Correct |
55 ms |
21540 KB |
Output is correct |
8 |
Correct |
52 ms |
21192 KB |
Output is correct |
9 |
Correct |
61 ms |
22212 KB |
Output is correct |
10 |
Correct |
52 ms |
21440 KB |
Output is correct |
11 |
Correct |
53 ms |
21940 KB |
Output is correct |
12 |
Correct |
50 ms |
21324 KB |
Output is correct |
13 |
Correct |
55 ms |
21704 KB |
Output is correct |
14 |
Correct |
53 ms |
21320 KB |
Output is correct |
15 |
Correct |
60 ms |
21468 KB |
Output is correct |
16 |
Correct |
57 ms |
21348 KB |
Output is correct |
17 |
Correct |
54 ms |
21440 KB |
Output is correct |
18 |
Correct |
544 ms |
163748 KB |
Output is correct |
19 |
Correct |
536 ms |
162884 KB |
Output is correct |
20 |
Correct |
629 ms |
164096 KB |
Output is correct |
21 |
Correct |
56 ms |
21448 KB |
Output is correct |
22 |
Correct |
53 ms |
22236 KB |
Output is correct |
23 |
Correct |
101 ms |
40532 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
56 ms |
22000 KB |
Output is correct |
3 |
Correct |
58 ms |
21448 KB |
Output is correct |
4 |
Correct |
659 ms |
162740 KB |
Output is correct |
5 |
Correct |
80 ms |
21440 KB |
Output is correct |
6 |
Correct |
61 ms |
21460 KB |
Output is correct |
7 |
Correct |
62 ms |
21440 KB |
Output is correct |
8 |
Correct |
57 ms |
21336 KB |
Output is correct |
9 |
Correct |
57 ms |
21440 KB |
Output is correct |
10 |
Correct |
57 ms |
21452 KB |
Output is correct |
11 |
Correct |
58 ms |
21400 KB |
Output is correct |
12 |
Correct |
53 ms |
21952 KB |
Output is correct |
13 |
Correct |
60 ms |
21696 KB |
Output is correct |
14 |
Correct |
583 ms |
163644 KB |
Output is correct |
15 |
Correct |
49 ms |
20924 KB |
Output is correct |
16 |
Correct |
531 ms |
163168 KB |
Output is correct |
17 |
Correct |
507 ms |
164196 KB |
Output is correct |
18 |
Correct |
0 ms |
2392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
2392 KB |
Output is correct |
2 |
Correct |
5 ms |
4060 KB |
Output is correct |
3 |
Correct |
5 ms |
4064 KB |
Output is correct |
4 |
Correct |
0 ms |
2396 KB |
Output is correct |
5 |
Correct |
1 ms |
2480 KB |
Output is correct |
6 |
Correct |
0 ms |
2396 KB |
Output is correct |
7 |
Correct |
0 ms |
2652 KB |
Output is correct |
8 |
Correct |
1 ms |
2396 KB |
Output is correct |
9 |
Correct |
1 ms |
2396 KB |
Output is correct |
10 |
Correct |
0 ms |
2396 KB |
Output is correct |
11 |
Correct |
0 ms |
2396 KB |
Output is correct |
12 |
Incorrect |
0 ms |
2396 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |