#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 / B - l / B + 1 > 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);
query.pb(Query(l / B % C, nr / B % C, 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) {
query.pb(Query(l / B % C, nr / B % C, l % B, nr % B));
l = nr + 1;
}
}
if (l > r) continue;
query.pb(Query(l / B % C, r / B % C, 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);
int pre = -1;
FOR(i, 0, m - 1) {
bool type = e[i].type;
ll t = e[i].t, l1 = e[i].l1, r1 = e[i].r1;
upd(1, 0, B - 1, l1, r1, type == 0? 1 : -1);
if (i < m && e[i + 1].type == type && e[i + 1].t == t) continue;
rs += f[1] * (t - pre);
pre = t;
}
rs += f[1] * (B - 1 - pre);
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;
}
return 0;
}
/*
3 5 10
1 20
50 68
89 98
*/
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:127:3: note: in expansion of macro 'EACH'
127 | 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:135:3: note: in expansion of macro 'FOR'
135 | FOR(i, 0, m - 1) {
| ^~~
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:152:5: note: in expansion of macro 'FOR'
152 | FOR(i, 1, n) {
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
2276 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 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 |
340 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
852 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
798 ms |
125196 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
798 ms |
125196 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
798 ms |
125196 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
118 ms |
17204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
2276 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
