#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 {
struct Node {
ll mid;
int cnt;
ll mrk;
Node *left, *right;
Node() : mid(0), cnt(0), mrk(0), left(0), right(0) {}
Node(ll mid, int cnt, ll mrk, Node *left, Node *right) : mid(mid), cnt(0), mrk(0), left(left), right(right) {}
};
vector<Query> query;
vector<Event> e;
ll rs = 0;
Node *root;
map<ll, bool> c;
vll v;
void build(Node *cur, ll nl, ll nr) {
int l = lb(all(v), nl) - v.begin(), r = ub(all(v), nr) - v.begin() - 1;
if (l > r) return;
if (l == r) {
if (nl == nr) return;
if (nl == v[l]) {
Node *left = new Node(0, 0, 0, 0, 0);
Node *right = new Node(0, 0, 0, 0, 0);
cur -> left = left;
cur -> right = right;
cur -> mid = v[l];
build(cur -> left, nl, v[l]);
build(cur -> right, v[l] + 1, nr);
return;
}
if (nr == v[l]) {
Node *left = new Node(0, 0, 0, 0, 0);
Node *right = new Node(0, 0, 0, 0, 0);
cur -> left = left;
cur -> right = right;
cur -> mid = v[l] - 1;
build(cur -> left, nl, v[l] - 1);
build(cur -> right, v[l], nr);
return;
}
return;
}
int mid = (l + r) / 2;
Node *left = new Node(0, 0, 0, 0, 0);
Node *right = new Node(0, 0, 0, 0, 0);
cur -> left = left;
cur -> right = right;
cur -> mid = v[mid];
build(cur -> left, nl, v[mid]);
build(cur -> right, v[mid] + 1, nr);
}
void upd(Node *cur, ll l, ll r, ll ql, ll qr, int v) {
if (r < ql || l > qr) return;
if (ql <= l && r <= qr) {
cur -> cnt += v;
cur -> mrk =
(cur -> cnt? r - l + 1 : (cur -> left? cur -> left -> mrk : 0) + (cur -> right? cur -> right -> mrk : 0));
return;
}
if (cur -> left) upd(cur -> left, l, cur -> mid, ql, qr, v);
if (cur -> right) upd(cur -> right, cur -> mid + 1, r, ql, qr, v);
cur -> mrk = (cur -> cnt? r - l + 1 : (cur -> left? cur -> left -> mrk : 0) + (cur -> right? cur -> right -> mrk : 0));
}
void solve() {
ll C = A / gcd(A, B + 1);
FOR(i, 1, n) {
ll l = a[i].st, r = a[i].nd;
if ((ldb)(r - l + 1) / C >= B) {
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;
if (!c.count(l1)) {
v.pb(l1);
c[l1] = 1;
}
if (!c.count(r1)) {
v.pb(r1);
c[r1] = 1;
}
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;
sort(all(v));
root = new Node(0, 0, 0, 0, 0);
build(root, v[0], v[sz(v) - 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 += root -> mrk * (t - pre);
}
upd(root, v[0], v[sz(v) - 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 += root -> mrk * (t - pre);
}
pre = t;
}
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();
// cerr << "\nTime: " << setprecision(6) << fixed << (ldb)clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}
/*
2 920016 914385
34129 655405
1212938 1781362
*/
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:232:3: note: in expansion of macro 'FOR'
232 | 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:239:3: note: in expansion of macro 'FOR'
239 | 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:272:3: note: in expansion of macro 'EACH'
272 | 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:291:3: note: in expansion of macro 'FOR'
291 | 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:313:5: note: in expansion of macro 'FOR'
313 | FOR(i, 1, n) {
| ^~~
strange_device.cpp:310:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
310 | freopen(file".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:311:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
311 | freopen(file".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
