#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;
const int INFF = 2e18;
struct node {
int val, lz;
int st, en, len;
node *left, *right;
void build(int start, int end) {
st = start;
en = end;
len = en - st + 1;
val = 0;
lz = 0;
}
void lazy() {
if (left == NULL && right == NULL) {
left = new node();
right = new node();
int md = (st + en) / 2;
left->build(st, md);
right->build(md + 1, en);
}
if (lz == 1) {
left->lz = lz;
left->val = lz * left->len;
right->lz = lz;
right->val = lz * right->len;
lz = 0;
}
}
void update(int lf, int rg) {
if (st > rg || en < lf) return;
if (lf <= st && en <= rg) {
lz = 1;
val = len;
return;
}
lazy();
left->update(lf, rg);
right->update(lf, rg);
val = left->val + right->val;
}
} sg;
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, a, b;
cin >> n >> a >> b;
/*
0 0 0 0
1 1 1 1
2 2 2 2
4 3 1 0
5 4 2 1
6 5 0 2
8 6 2 0
9 7 0 1
10 8 1 2
12 9 0 0
*/
if (a > INFF / b) {
sg.build(0, INFF);
} else {
sg.build(0, a * b - 1);
}
for (int i = 0; i < n; i++) {
int l, r;
cin >> l >> r;
if (a <= INFF / b && r - l + 1 >= a * b) {
cout << a * b << '\n';
return 0;
}
if (a <= INFF / b) {
l %= a * b;
r %= a * b;
}
if (l <= r) {
// cout << l << " " << r << '\n';
sg.update(l, r);
} else {
// cout << l << " " << a * b - 1 << '\n';
sg.update(l, a * b - 1);
// cout << 0 << " " << r << '\n';
sg.update(0, r);
}
}
cout << sg.val << '\n';
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
8 ms |
5836 KB |
Output is correct |
3 |
Correct |
10 ms |
6868 KB |
Output is correct |
4 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
324 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
2 ms |
1748 KB |
Output is correct |
3 |
Correct |
2 ms |
1872 KB |
Output is correct |
4 |
Correct |
2 ms |
1748 KB |
Output is correct |
5 |
Correct |
287 ms |
744 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
463 ms |
126568 KB |
Output is correct |
3 |
Runtime error |
611 ms |
524288 KB |
Execution killed with signal 9 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
463 ms |
126568 KB |
Output is correct |
3 |
Runtime error |
611 ms |
524288 KB |
Execution killed with signal 9 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
463 ms |
126568 KB |
Output is correct |
3 |
Runtime error |
611 ms |
524288 KB |
Execution killed with signal 9 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
125 ms |
88192 KB |
Output is correct |
3 |
Correct |
212 ms |
201068 KB |
Output is correct |
4 |
Runtime error |
514 ms |
524288 KB |
Execution killed with signal 9 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
8 ms |
5836 KB |
Output is correct |
3 |
Correct |
10 ms |
6868 KB |
Output is correct |
4 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |