#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ss second
#define ff first
#define pb push_back
#define pii pair<int, int>
#define INF INT_MAX
#define debug(n) cout << #n << " = " << n << "\n";
#define FAST ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const ll MOD = 1e9 + 7;
int main() {
ll n, A, B;
cin >> n >> A >> B;
unordered_map<ll, vector<pair<ll, ll> > > umap;
map<ll, ll> fullset;
ll L = 0;
for(int i = 0; i < n; i++) {
ll l, r;
cin >> l >> r;
L += r - l + 1;
if(l / B != r / B) {
// cout << (l / B) << " " << (r / B) << " these values are inserted\n";
umap[(l / B)].pb({l % B, B - 1});
umap[(r / B)].pb({0, r % B});
} else {
umap[(l / B)].pb({l % B, r % B});
// cout << (l / B) << " inserted\n";
}
fullset[l / B + 1]++;
fullset[r / B]--;
}
ll prev = 0;
vector<pair<ll, ll > > fset;
for(auto el : fullset) {
prev += el.ss;
// cout << el.ff << " " << el.ss << " fset" << "\n";
fset.pb({el.ff, prev});
}
// for(auto el : fset) {
// cout << el.ff << " " << el.ss << "\n";
// }
map<ll, ll> fs;
// cut
for(int i = 0; i < fset.size() - 1; i++) {
if(fset[i].ff / A != fset[i + 1].ff / A) {
fs[fset[i].ff % A] += fset[i].ss;
fs[A] -= fset[i].ss;
fs[0] += fset[i].ss;
fs[fset[i + 1].ff % A] -= fset[i].ss;
fs[0] += (fset[i + 1].ff / A - fset[i].ff / A - 1);
fs[A] -= (fset[i + 1].ff / A - fset[i].ff / A - 1);
} else {
fs[fset[i].ff % A] += fset[i].ss;
fs[fset[i + 1].ff % A] -= fset[i].ss;
}
}
prev = 0;
vector<pair<ll, ll> > nfset;
for(auto el : fs) {
// cout << el.ff << " " << el.ss << " fs elements\n";
prev += el.ss;
nfset.pb({el.ff, prev});
}
// debug(L);
if(nfset.size() > 0) {
for(int i = 1; i < nfset.size(); i++) {
// cout << nfset[i - 1].ff << " " << nfset[i].ff << " segment have " << nfset[i - 1].ss << " elements wtf ? \n";
L -= (nfset[i].ff - nfset[i - 1].ff) * max(nfset[i - 1].ss - 1, 0LL);
nfset[i - 1].ss = min(nfset[i - 1].ss, 1LL);
}
nfset.back().ss = min(nfset.back().ss, 1LL); // ?
}
// debug(L);
unordered_map<ll, bool> calculated;
unordered_map<ll, vector<pair<ll, ll> > > umapmod;
for(auto el : umap) {
for(auto x : el.ss)
umapmod[el.ff % A].pb(x);
}
for(auto el : umap) {
if(calculated[el.ff % A] == 1) {
continue;
}
// cout << el.ff << " first \n";
vector<pair<ll, ll> > segments = umapmod[el.ff % A];
// for(auto e : segments) {
// cout << e.ff << " " << e.ss << " seg\n";
// }
pair<ll, ll> f = {el.ff % A, INT64_MAX};
// cout << "index : " << int(upper_bound(fset.begin(), fset.end(), f) - fset.begin()) - 1 << "\n";
int ind = int(upper_bound(nfset.begin(), nfset.end(), f) - nfset.begin()) - 1;
ll full = (ind >= 0 ? nfset[ind].ss : 0);
map<ll, ll> m;
for(auto seg : segments) {
m[seg.ff]++;
m[seg.ss + 1]--;
}
prev = 0;
vector<pair<ll, ll> > line;
for(auto e : m) {
prev += e.ss;
line.pb({e.ff, prev});
}
// debug(full);
// cout << "--------------------------\ncalculating .. \n";
for(int i = 1; i < line.size(); i++) {
ll cnt = line[i].ff - line[i - 1].ff;
// cout << line[i - 1].ff << " " << line[i].ff << " this segment have " << line[i - 1].ss - 1 + full << " multiple elements\n";
L -= cnt * max(line[i - 1].ss - 1 + full, 0LL);
}
// cout << "done .. L = " << L << "\n";
calculated[el.ff % A] = 1;
}
cout << L << "\n";
return 0;
}
/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
*/
Compilation message
strange_device.cpp: In function 'int main()':
strange_device.cpp:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int i = 0; i < fset.size() - 1; i++) {
| ~~^~~~~~~~~~~~~~~~~
strange_device.cpp:72:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for(int i = 1; i < nfset.size(); i++) {
| ~~^~~~~~~~~~~~~~
strange_device.cpp:116:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | for(int i = 1; i < line.size(); i++) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
19 ms |
1040 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
844 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
3230 ms |
369476 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
3230 ms |
369476 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
3230 ms |
369476 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
170 ms |
4348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
19 ms |
1040 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
