#include "bits/stdc++.h"
using namespace std;
#define ar array
#define i128 __int128
#define int long long
int bp(int a, int b, int mod){
int r = 1;
while(b){
if(b&1){
r = (i128)r * (i128)a % mod;
} a = (i128)a * (i128)a % mod, b >>= 1;
} return r;
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n, A, B; cin>>n>>A>>B;
vector<ar<int, 2>> s(n);
for(int i=0;i<n;i++){
cin>>s[i][0]>>s[i][1];
}
int D = B + 1;
int G = __gcd(A, D);
vector<ar<int, 3>> ss;
vector<ar<int, 2>> big;
for(int i=0;i<n;i++){
int l = s[i][0], r = s[i][1];
int bl = l / B, br = r / B;
if(bl == br){
ss.push_back({l % B, r % B, (l + l/B) % A});
} else {
ss.push_back({l % B, B - 1, (l + l/B) % A});
int t = br * B;
ss.push_back({0, r % B, (t + t/B) % A});
int x = (bl + 1) * B, c = (br - bl - 1);
if(c){
big.push_back({(x + x/B) % A, c});
}
}
}
sort(big.begin(), big.end(), [&](auto& a, auto& b){
return (a[0] % G < b[0] % G);
});
sort(big.begin(), big.end(), [&](auto& a, auto& b){
return (a[2] % G < b[2] % G);
});
int res = 0;
auto just = [&](vector<ar<int, 3>>& ss, int A){
sort(ss.begin(), ss.end());
map<int, int> mm;
for(auto& x : ss){
x[2] /= G;
x[2] = (x[2] - x[0] % A + A) % A;
if(!mm.count(x[2])){
res += (x[1] - x[0] + 1), mm[x[2]] = x[1];
} else if(mm[x[2]] < x[1]) res += (x[1] - mm[x[2]]), mm[x[2]] = x[1];
}
};
auto solve = [&](vector<ar<int, 2>>& a, vector<ar<int, 3>>& ss, int A, int D){
if(A == 1){
res += B;
return;
}
vector<ar<int, 2>> tot;
for(auto& x : a){ x[0] /= G;
x[0] = (i128)x[0] * (i128)bp(D, A - 2, A) % A;
x[1] = (x[0] + x[1] - 1) % A;
if(x[0] <= x[1]) tot.push_back({x[0], x[1]});
else {
tot.push_back({x[0], A - 1});
tot.push_back({0, x[1]});
}
}
//~ [x[0], x[0] + c - 1]
sort(tot.begin(), tot.end());
int r = -1;
for(auto& x : tot){
if(r < x[1]){
res += (x[1] - max(r + 1, x[0]) + 1) * B;
r = x[1];
} x[1] = max(x[1], r);
}
sort(ss.begin(), ss.end());
map<int, int> mm;
for(auto& x : ss){
x[2] /= G;
x[2] = (x[2] - x[0] % A + A) % A;
auto it = upper_bound(tot.begin(), tot.end(), (ar<int, 2>){x[2] + 1, -1});
if(it != tot.begin()){
it--;
if(x[2] <= (*it)[1]) continue;
}
if(!mm.count(x[2])){
res += (x[1] - x[0] + 1), mm[x[2]] = x[1];
} else if(mm[x[2]] < x[1]) res += (x[1] - mm[x[2]]), mm[x[2]] = x[1];
}
};
int l = 0;
for(int i=0;i<(int)big.size();){
int j = i;
vector<ar<int, 2>> tt;
while(j < (int)big.size() && big[j][0]%G == big[i][0]%G) tt.push_back(big[j]), j++;
int v = big[i][0]%G;
i = j;
j = l;
vector<ar<int, 3>> tmp;
while(j < (int)ss.size() && ss[j][2]%G < v){
while(j < (int)ss.size() && ss[j][2]%G == ss[l][2]%G){
tmp.push_back(ss[j]);
j++;
} l = j;
just(tmp, A / G);
tmp.clear();
}
while(j < (int)ss.size() && ss[j][2]%G == v){
tmp.push_back(ss[j]);
j++;
} l = j;
solve(tt, tmp, A / G, D / G);
}
while(l < (int)ss.size()){
int j = l;
vector<ar<int, 3>> tmp;
while(j < (int)ss.size() && ss[j][0]%G == ss[l][0]%G){
tmp.push_back(ss[j]);
j++;
} l = j;
just(tmp, A / G);
}
cout<<res<<"\n";
}
Compilation message
strange_device.cpp: In function 'void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::array<long long int, 2>*, std::vector<std::array<long long int, 2> > >; _Distance = long int; _Tp = std::array<long long int, 2>; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(auto:25&, auto:26&)> >]':
strange_device.cpp:50:27: warning: array subscript 2 is outside array bounds of 'std::array<long long int, 2> [1]' [-Warray-bounds]
50 | return (a[2] % G < b[2] % G);
| ~~~~~^~~
In file included from /usr/include/c++/10/bits/stl_algo.h:61,
from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from strange_device.cpp:1:
/usr/include/c++/10/bits/stl_heap.h:223:5: note: while referencing '__value'
223 | __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
| ^~~~~~~~~~~~~
strange_device.cpp: In function 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::array<long long int, 2>*, std::vector<std::array<long long int, 2> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(auto:25&, auto:26&)> >]':
strange_device.cpp:50:16: warning: array subscript 2 is outside array bounds of 'std::__iterator_traits<__gnu_cxx::__normal_iterator<std::array<long long int, 2>*, std::vector<std::array<long long int, 2> > >, void>::value_type [1]' {aka 'std::array<long long int, 2> [1]'} [-Warray-bounds]
50 | return (a[2] % G < b[2] % G);
| ~~~~~^~~
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from strange_device.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:1823:2: note: while referencing '__val'
1823 | __val = _GLIBCXX_MOVE(*__last);
| ^~~~~
strange_device.cpp: In function 'int main()':
strange_device.cpp:50:16: warning: array subscript 2 is outside array bounds of 'std::__iterator_traits<__gnu_cxx::__normal_iterator<std::array<long long int, 2>*, std::vector<std::array<long long int, 2> > >, void>::value_type [1]' {aka 'std::array<long long int, 2> [1]'} [-Warray-bounds]
50 | return (a[2] % G < b[2] % G);
| ~~~~~^~~
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from strange_device.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:1823:2: note: while referencing '__val'
1823 | __val = _GLIBCXX_MOVE(*__last);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
1616 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
312 KB |
Output is correct |
| 3 |
Correct |
1 ms |
316 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1300 ms |
162676 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1300 ms |
162676 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1300 ms |
162676 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
68 ms |
12480 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
1616 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
