#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 4000010;
long long res = 0;
int n;
long long A, B;
vector <pair <int, int>> opp[N];
long long gdc(long long x, long long y){
if(x < y) swap(x, y);
return (y == 0 ? x : gdc(y, x%y));
}
void corrigir(vector <pair <int, int>> &v){
vector <pair <int, int>> aux;
for(auto [l, r] : v){
if(r-l+1 >= A) {
aux.push_back({0, A-1});
continue;
}
l %= A;
r %= A;
if(l <= r) aux.push_back({l, r});
else{
aux.push_back({l, A-1});
aux.push_back({0,r});
}
}
v = aux;
sort(v.begin(), v.end());
aux.clear();
for(auto [l, r] : v){
//cout << l << ' ' << r << '\n';
if(!aux.empty()){
auto [a, b] = aux.back();
if(b < l) aux.push_back({l, r});
else{
aux.pop_back();
aux.push_back({a, max(b, r)});
}
}
else{
aux.push_back({l, r});
}
}
v = aux;
return;
}
int32_t main(){
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> A >> B;
A = A/gdc(A, B+1);
vector <pair <int, int>> queries;
vector <array <int, 3>> corners;
for(int i = 1;i <= n;i++){
int l, r;
cin >> l >> r;
if(r-l+1 <= B and r%B >= l%B){
int d = r/B;
corners.push_back({l%B, r%B, (d%A)});
continue;
}
if(l%B != 0){
int d = (l+B-1)/B;
corners.push_back({l%B, B-1, ((d-1)%A+A)%A});
}
int a = (l+B-1)/B;
int b = r/B;
if(r%B == B-1){
queries.push_back({a, b});
continue;
}
if(B*a <= B*b-1){
queries.push_back({a, b-1});
}
if(r%B != B-1){
corners.push_back({0, r%B, b%A});
}
}
corrigir(queries);
//set <int> s;
map <int, int> m;
map <int ,int> cnt;
int add = 0;
//cout << "cte:\n";
for(auto [l, r] : queries){
//cout << l << ' ' << r << '\n';
m[l] = r;
add += r-l+1;
//s.insert(l);
}
//cout << '\n';
set <int> valores;
for(auto [l, r, w] : corners){
//cout << l << ' ' << r << ' ' << w << '\n';
valores.insert(l);
valores.insert(r+1);
}
map <int, int> mapear;
int con = 0;
for(auto x : valores){
mapear[x] = con;
con++;
}
mapear[B] = con;
con++;
for(auto [l, r, w] : corners){
opp[mapear[l]].push_back({w, 0});
opp[mapear[r+1]].push_back({w, 1});
}
int st = 0;
vector <int> v;
for(auto [aa, bb] : m){
v.push_back(aa);
}
for(auto [pos, valor] : mapear){
res += (pos-st)*add;
st = pos;
for(auto [x, tp] : opp[valor]){
if(tp == 0){
int d = upper_bound(v.begin(), v.end(), x)-v.begin();
if(d == 0) continue;
d--;
if(m[v[d]] >= x) continue;
if(cnt[x] == 0) add++;
cnt[x]++;
}
else{
auto it = cnt.find(x);
if(it == cnt.end()) continue;
auto [_, d] = *it;
if(d == 1){
cnt.erase(it);
add--;
continue;
}
cnt[x]--;
}
}
//cout << add << '\n';
}
cout << res << '\n';
return 0;
}
/*
10 7 1
3 5
8 11
26 33
40 52
65 69
83 95
113 123
135 136
154 166
182 185
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
94280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
94284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
58 ms |
94248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
72 ms |
94280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
72 ms |
94280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
72 ms |
94280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
69 ms |
94280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
94280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
