//0 1 1 0 1
//0 1 0 0 1
//1 0 0 1 1
//0 1 1 0 1
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
#define F first
#define S second
#define pb push_back
#define sze size()
#define all(x) x.begin() , x.end()
#define wall__ cout << "--------------------------------------\n";
#define kids int mid = (tl + tr) >> 1, cl = v << 1, cr = v << 1 | 1
#define file_io freopen("input.cpp", "r", stdin); freopen("output.cpp", "w", stdout);
typedef long long ll;
typedef long double dl;
typedef pair < int , int > pii;
typedef pair < int , ll > pil;
typedef pair < ll , int > pli;
typedef pair < ll , ll > pll;
typedef pair < int , pii > piii;
typedef pair < ll, pll > plll;
const ll N = 2e5 + 10;
const ll mod = 1e9 + 7;
const ll inf = 2e18;
const ll rinf = -2e16;
const ll INF = 1e9 + 10;
const ll rINF = -1e9 - 10;
const ll lg = 32;
set < plll > s;
plll find (int id) {
auto it = s.lower_bound({id + 1ll, {0, 0}});
it = prev(it);
return *it;
}
void add (ll l, ll r) {
plll x = find(l);
if (x.F < l) {
s.erase(x);
s.insert({x.F, {l - 1ll, x.S.S}});
s.insert({l, x.S});
}
x = find(r);
if (x.S.F > r) {
s.erase(x);
s.insert({x.F, {r, x.S.S}});
s.insert({r + 1ll, x.S});
}
x = *s.lower_bound({l, {0, 0}});
while (x.F <= r) {
s.erase(x);
if (x.S.F == r) break;
x = *s.lower_bound({l, {0, 0}});
}
s.insert({l, {r, 1}});
}
void solve () {
int n;
ll A, B;
cin >> n >> A >> B;
dl a = A, b = (B + 1ll);
dl x = __gcd(A, B + 1ll);
dl lcm = (a * b) / x;
dl y = lcm / b;
dl bb = B;
dl z = y * bb;
ll t;
if (z > 1e18) t = 1e8;
else t = z;
s.insert({0, {t - 1ll, 0}});
s.insert({inf, {inf, inf}});
s.insert({-1, {-1, -1}});
bool ch = 0;
ll en = t - 1ll;
for (int i = 1; i <= n; i++) {
ll l, r; cin >> l >> r;
ll len = (r - l + 1ll);
if (len >= t) {
ch = 1;
add(0, en);
}
if (ch) continue;
l = l % t;
r = r % t;
if (l <= r) add(l, r);
else {
add(l, en);
add(0, r);
}
}
ll ans = 0;
for (auto it = s.begin(); it != s.end(); ++it) {
plll x = *it;
if (x.S.S == 1) ans += (x.S.F - x.F + 1ll);
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t = 1;
// cin >> t;
while (t--) {solve();}
return 0;
}
/*
*/
//inhonorofsbi;
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
12 ms |
924 KB |
Output is correct |
3 |
Correct |
12 ms |
872 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
10 ms |
852 KB |
Output is correct |
17 |
Correct |
151 ms |
6548 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 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 |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
2 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
340 KB |
Output is correct |
4 |
Correct |
2 ms |
340 KB |
Output is correct |
5 |
Correct |
311 ms |
300 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1536 ms |
62800 KB |
Output is correct |
3 |
Incorrect |
1815 ms |
70600 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1536 ms |
62800 KB |
Output is correct |
3 |
Incorrect |
1815 ms |
70600 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1536 ms |
62800 KB |
Output is correct |
3 |
Incorrect |
1815 ms |
70600 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
146 ms |
6500 KB |
Output is correct |
3 |
Incorrect |
149 ms |
9248 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
12 ms |
924 KB |
Output is correct |
3 |
Correct |
12 ms |
872 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
10 ms |
852 KB |
Output is correct |
17 |
Correct |
151 ms |
6548 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
0 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
212 KB |
Output is correct |
24 |
Correct |
1 ms |
212 KB |
Output is correct |
25 |
Correct |
2 ms |
340 KB |
Output is correct |
26 |
Correct |
2 ms |
340 KB |
Output is correct |
27 |
Correct |
2 ms |
340 KB |
Output is correct |
28 |
Correct |
311 ms |
300 KB |
Output is correct |
29 |
Correct |
1 ms |
212 KB |
Output is correct |
30 |
Correct |
1536 ms |
62800 KB |
Output is correct |
31 |
Incorrect |
1815 ms |
70600 KB |
Output isn't correct |
32 |
Halted |
0 ms |
0 KB |
- |