#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.h>
#endif
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
template<typename T> T gcd(T a, T b) { return (b == 0? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
#define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
#define EACH(i, x) for (auto &(i) : (x))
#define WHILE while
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
Tran The Bao
CTL - Da Lat
Cay ngay cay dem nhung deo duoc cong nhan
*/
const int N = 1e6 + 1;
int n;
ll A, B, S = 0, L = 0;
pll a[N];
namespace subtask1 {
map<pll, bool> d;
void solve() {
int rs = 0;
FOR(i, 1, n) {
ll l = a[i].st, r = a[i].nd;
for (ll t = l; t <= r; ++t) {
ll x = (t + t / B) % A, y = t % B;
if (d.count({x, y})) continue;
d[{x, y}] = 1;
++rs;
}
}
cout << rs;
}
}
namespace subtask2 {
ll rs = 0;
void solve() {
ll l = a[1].st, r = a[1].nd;
ll C = A / gcd(A, B + 1);
ll pr = max(r - (r % B - l % B + B) % B - 1, l - 1);
rs += (r - pr) * min((r - l + 1) / B + 1, C);
rs += (min(B, r - l + 1) - r + pr) * min(r / B - l / B, C);
cout << rs;
}
}
struct Query {
ll l, r, l1, r1;
Query() {}
Query(ll l, ll r, ll l1, ll r1) : l(l), r(r), l1(l1), r1(r1) {}
};
struct Event {
bool type;
ll t, l1, r1;
Event() {}
Event(bool type, ll t, ll l1, ll r1) : type(type), t(t), l1(l1), r1(r1) {}
};
bool cmp(Event &a, Event &b) {
if (a.t != b.t) return a.t < b.t;
return a.type < b.type;
}
namespace subtask3456 {
const int T = 4e6 + 1;
vector<Query> query;
vector<Event> e;
int tr[T], f[T];
ll rs = 0;
void upd(int i, int l, int r, int ql, int qr, int v) {
if (r < ql || l > qr) return;
if (ql <= l && r <= qr) {
tr[i] += v;
f[i] = (tr[i]? r - l + 1 : l != r? f[i * 2] + f[i * 2 + 1] : 0);
return;
}
int mid = l + (r - l) / 2;
upd(i * 2, l, mid, ql, qr, v);
upd(i * 2 + 1, mid + 1, r, ql, qr, v);
f[i] = (tr[i]? r - l + 1 : l != r? f[i * 2] + f[i * 2 + 1] : 0);
}
void solve() {
ll C = A / gcd(A, B + 1);
FOR(i, 1, n) {
ll l = a[i].st, r = a[i].nd;
if ((r - l + 1) >= B * C) {
cout << B * C;
return;
}
}
FOR(i, 1, n) {
ll l = a[i].st, r = a[i].nd;
if (l % B != 0) {
ll nr = min(r, l + B - 1 - l % B);
ll l1 = l / B % C, r1 = nr / B % C;
if (l1 <= r1) query.pb(Query(l1, r1, l % B, nr % B));
else {
query.pb(Query(l1, C - 1, l % B, nr % B));
query.pb(Query(0, r1, l % B, nr % B));
}
l = nr + 1;
}
if (l > r) continue;
if (r % B != B - 1) {
ll nr = r - (r % B) - 1;
if (l <= nr) {
ll l1 = l / B % C, r1 = nr / B % C;
if (l1 <= r1) query.pb(Query(l1, r1, l % B, nr % B));
else {
query.pb(Query(l1, C - 1, l % B, nr % B));
query.pb(Query(0, r1, l % B, nr % B));
}
l = nr + 1;
}
}
if (l > r) continue;
ll l1 = l / B % C, r1 = r / B % C;
if (l1 <= r1) query.pb(Query(l1, r1, l % B, r % B));
else {
query.pb(Query(l1, C - 1, l % B, r % B));
query.pb(Query(0, r1, l % B, r % B));
}
}
EACH(i, query) {
ll l = i.l, r = i.r, l1 = i.l1, r1 = i.r1;
e.pb(Event(0, l, l1, r1));
e.pb(Event(1, r, l1, r1));
}
sort(all(e), cmp);
int m = sz(e);
ll pre = e[0].t - 1;
FOR(i, 0, m - 1) {
bool type = e[i].type;
ll t = e[i].t, l1 = e[i].l1, r1 = e[i].r1;
if (type == 1 && (i == 0 || e[i - 1].type == 0 || e[i - 1].t != t)) {
rs += f[1] * (t - pre);
}
upd(1, 0, B - 1, l1, r1, type == 0? 1 : -1);
if (type == 0 && i > 0 && e[i - 1].type == 1) pre = e[i].t - 1;
if (i < m - 1 && e[i + 1].type == type && e[i + 1].t == t) continue;
if (type == 0) {
rs += f[1] * (t - pre);
}
pre = t;
}
cout << rs;
}
}
namespace subtask78 {
ll rs = 0;
vpll b;
void solve() {
ll g = gcd(A, B + 1), C;
if (A / g > 2e18 / B) C = 2e18;
else C = A / g * B;
FOR(i, 1, n) {
ll l = a[i].st, r = a[i].nd;
if (r - l + 1 >= C) {
cout << C;
return;
}
l %= C;
r %= C;
if (l <= r) b.pb({l, r});
else {
b.pb({l, C - 1});
b.pb({0, r});
}
}
sort(all(b));
ll pre = -1;
EACH(i, b) {
ll l = i.st, r = i.nd;
if (pre < l) {
rs += r - l + 1;
pre = r;
}
else if (r > pre) {
rs += r - pre;
pre = r;
}
pre = r;
}
cout << rs;
}
}
signed main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
// freopen(file".inp", "r", stdin);
// freopen(file".out", "w", stdout);
cin >> n >> A >> B;
FOR(i, 1, n) {
cin >> a[i].st >> a[i].nd;
S += a[i].nd - a[i].st + 1;
L = max(L, a[i].nd - a[i].st + 1);
}
if (S <= 1e6) {
subtask1::solve();
return 0;
}
if (n == 1) {
subtask2::solve();
return 0;
}
if (B <= 1e6) {
subtask3456::solve();
return 0;
}
subtask78::solve();
return 0;
}
/*
3 8 2
5 7
13 23
24 33
*/
Compilation message
strange_device.cpp: In function 'void subtask1::solve()':
strange_device.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
strange_device.cpp:44:3: note: in expansion of macro 'FOR'
44 | FOR(i, 1, n) {
| ^~~
strange_device.cpp: In function 'void subtask3456::solve()':
strange_device.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
strange_device.cpp:102:3: note: in expansion of macro 'FOR'
102 | FOR(i, 1, n) {
| ^~~
strange_device.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
strange_device.cpp:109:3: note: in expansion of macro 'FOR'
109 | FOR(i, 1, n) {
| ^~~
strange_device.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
26 | #define EACH(i, x) for (auto &(i) : (x))
| ^
strange_device.cpp:142:3: note: in expansion of macro 'EACH'
142 | EACH(i, query) {
| ^~~~
strange_device.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
strange_device.cpp:150:3: note: in expansion of macro 'FOR'
150 | FOR(i, 0, m - 1) {
| ^~~
strange_device.cpp: In function 'void subtask78::solve()':
strange_device.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
strange_device.cpp:174:3: note: in expansion of macro 'FOR'
174 | FOR(i, 1, n) {
| ^~~
strange_device.cpp:26:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
26 | #define EACH(i, x) for (auto &(i) : (x))
| ^
strange_device.cpp:190:3: note: in expansion of macro 'EACH'
190 | EACH(i, b) {
| ^~~~
strange_device.cpp: In function 'int main()':
strange_device.cpp:24:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
24 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
| ^
strange_device.cpp:210:5: note: in expansion of macro 'FOR'
210 | FOR(i, 1, n) {
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
58 ms |
12444 KB |
Output is correct |
3 |
Correct |
83 ms |
18024 KB |
Output is correct |
4 |
Correct |
3 ms |
852 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
8 ms |
1244 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
44 ms |
7024 KB |
Output is correct |
16 |
Correct |
35 ms |
6904 KB |
Output is correct |
17 |
Correct |
61 ms |
8140 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
162 ms |
32356 KB |
Output is correct |
3 |
Correct |
199 ms |
32088 KB |
Output is correct |
4 |
Correct |
146 ms |
30540 KB |
Output is correct |
5 |
Correct |
480 ms |
113108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
758 ms |
113080 KB |
Output is correct |
3 |
Correct |
808 ms |
113060 KB |
Output is correct |
4 |
Correct |
765 ms |
113048 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
758 ms |
113080 KB |
Output is correct |
3 |
Correct |
808 ms |
113060 KB |
Output is correct |
4 |
Correct |
765 ms |
113048 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
2078 ms |
372680 KB |
Output is correct |
7 |
Correct |
784 ms |
113176 KB |
Output is correct |
8 |
Correct |
1898 ms |
372676 KB |
Output is correct |
9 |
Correct |
2296 ms |
372644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
758 ms |
113080 KB |
Output is correct |
3 |
Correct |
808 ms |
113060 KB |
Output is correct |
4 |
Correct |
765 ms |
113048 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
120 ms |
24632 KB |
Output is correct |
7 |
Correct |
197 ms |
44260 KB |
Output is correct |
8 |
Correct |
184 ms |
44292 KB |
Output is correct |
9 |
Correct |
185 ms |
44268 KB |
Output is correct |
10 |
Correct |
117 ms |
23824 KB |
Output is correct |
11 |
Correct |
192 ms |
44228 KB |
Output is correct |
12 |
Correct |
175 ms |
44212 KB |
Output is correct |
13 |
Correct |
223 ms |
44328 KB |
Output is correct |
14 |
Correct |
136 ms |
27816 KB |
Output is correct |
15 |
Correct |
209 ms |
24888 KB |
Output is correct |
16 |
Correct |
181 ms |
27948 KB |
Output is correct |
17 |
Correct |
280 ms |
46608 KB |
Output is correct |
18 |
Correct |
2263 ms |
372736 KB |
Output is correct |
19 |
Correct |
2128 ms |
372720 KB |
Output is correct |
20 |
Correct |
2812 ms |
372768 KB |
Output is correct |
21 |
Correct |
254 ms |
44196 KB |
Output is correct |
22 |
Correct |
167 ms |
44196 KB |
Output is correct |
23 |
Correct |
198 ms |
49376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
109 ms |
13504 KB |
Output is correct |
3 |
Correct |
46 ms |
4032 KB |
Output is correct |
4 |
Incorrect |
457 ms |
32476 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
58 ms |
12444 KB |
Output is correct |
3 |
Correct |
83 ms |
18024 KB |
Output is correct |
4 |
Correct |
3 ms |
852 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
8 ms |
1244 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
44 ms |
7024 KB |
Output is correct |
16 |
Correct |
35 ms |
6904 KB |
Output is correct |
17 |
Correct |
61 ms |
8140 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
0 ms |
340 KB |
Output is correct |
23 |
Correct |
0 ms |
212 KB |
Output is correct |
24 |
Correct |
0 ms |
212 KB |
Output is correct |
25 |
Correct |
162 ms |
32356 KB |
Output is correct |
26 |
Correct |
199 ms |
32088 KB |
Output is correct |
27 |
Correct |
146 ms |
30540 KB |
Output is correct |
28 |
Correct |
480 ms |
113108 KB |
Output is correct |
29 |
Correct |
0 ms |
212 KB |
Output is correct |
30 |
Correct |
758 ms |
113080 KB |
Output is correct |
31 |
Correct |
808 ms |
113060 KB |
Output is correct |
32 |
Correct |
765 ms |
113048 KB |
Output is correct |
33 |
Correct |
0 ms |
212 KB |
Output is correct |
34 |
Correct |
2078 ms |
372680 KB |
Output is correct |
35 |
Correct |
784 ms |
113176 KB |
Output is correct |
36 |
Correct |
1898 ms |
372676 KB |
Output is correct |
37 |
Correct |
2296 ms |
372644 KB |
Output is correct |
38 |
Correct |
0 ms |
340 KB |
Output is correct |
39 |
Correct |
120 ms |
24632 KB |
Output is correct |
40 |
Correct |
197 ms |
44260 KB |
Output is correct |
41 |
Correct |
184 ms |
44292 KB |
Output is correct |
42 |
Correct |
185 ms |
44268 KB |
Output is correct |
43 |
Correct |
117 ms |
23824 KB |
Output is correct |
44 |
Correct |
192 ms |
44228 KB |
Output is correct |
45 |
Correct |
175 ms |
44212 KB |
Output is correct |
46 |
Correct |
223 ms |
44328 KB |
Output is correct |
47 |
Correct |
136 ms |
27816 KB |
Output is correct |
48 |
Correct |
209 ms |
24888 KB |
Output is correct |
49 |
Correct |
181 ms |
27948 KB |
Output is correct |
50 |
Correct |
280 ms |
46608 KB |
Output is correct |
51 |
Correct |
2263 ms |
372736 KB |
Output is correct |
52 |
Correct |
2128 ms |
372720 KB |
Output is correct |
53 |
Correct |
2812 ms |
372768 KB |
Output is correct |
54 |
Correct |
254 ms |
44196 KB |
Output is correct |
55 |
Correct |
167 ms |
44196 KB |
Output is correct |
56 |
Correct |
198 ms |
49376 KB |
Output is correct |
57 |
Correct |
1 ms |
212 KB |
Output is correct |
58 |
Correct |
109 ms |
13504 KB |
Output is correct |
59 |
Correct |
46 ms |
4032 KB |
Output is correct |
60 |
Incorrect |
457 ms |
32476 KB |
Output isn't correct |
61 |
Halted |
0 ms |
0 KB |
- |