#include <bits/stdc++.h>
#define MAXN 1001001
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair< pair<ll,ll> , pair<ll,ll> > ter;
vector < ter > vct;
int n;
ll A , B , D ,l[MAXN] , r[MAXN];
ll gcd(ll a , ll b){
if(a > b) swap(a,b);
if(a == 0) return b;
return gcd(a , b%a);
}
int equall(pll a, pll b){
if(a.x == b.x && a.y == b.y) return 2;
if(a.x == b.x) return a.y > b.y;
return a.x > b.x;
}
pll nxt(pll a){
if(a.y == B-1 && a.x == D-1) return {0,0};
if(a.y == B-1) return {a.x+1 , 0};
return pll(a.x , a.y+1);
}
pll mx(pll a , pll b){
if(a.x == b.x){
if(a.y >b.y) return a;
else return b;
}
else{
if(a.x > b.x) return a;
else return b;
}
}
ll dist(pll a , pll b){
ll u = a.x*B + a.y , v = b.x*B + b.y;
if(v-u+1ll > 0) return (ll)v-u+1ll;
return 0;
}
int main(){
cin >> n >> A >> B;
//cout << gcd(100000 , 3) << endl;
ll D = A / gcd(A, B+1);
for(int i=0; i<n; i++){
cin >> l[i] >> r[i];
ll a1 = l[i]/B , a2 = l[i]%B , b1 = r[i]/B , b2 = r[i]%B;
if(r[i] - l[i] + 1 >= D*B) vct.push_back({{0,0} , {D-1,B-1}});
else{
a1 = a1%D , b1 = b1%D;
if(a1 > b1 || (a1 == b1 && a2 > b2)){
vct.push_back({{a1,a2} , {D-1,B-1}});
vct.push_back({{0ll,0ll} , {b1,b2}});
}
else vct.push_back({{a1,a2} , {b1,b2}});
}
}
sort(vct.begin() , vct.end());
/*for(int i=0; i<vct.size(); i++){
cout << vct[i].x.x << "," << vct[i].x.y << "," << vct[i].y.x << "," << vct[i].y.y << " " ;
}
cout << endl;*/
pll cur = pll(-1ll , -1ll);
for(int i=0; i<vct.size(); i++){
if(equall(cur , vct[i].first)){ ///0 greater is vct[i] , 1 greater is cur , 2 are eqial
vct[i].first = nxt(cur);
}
cur = mx(vct[i].second , cur);
}
/*for(int i=0; i<vct.size(); i++){
cout << vct[i].x.x << "," << vct[i].x.y << "," << vct[i].y.x << "," << vct[i].y.y << " " ;
}
cout << endl;*/
ll ans = 0;
for(int i=0; i<vct.size(); i++){
if(equall(vct[i].y , vct[i].x)) ans += dist(vct[i].first , vct[i].second);
}
cout << ans << endl;
return 0;
}
Compilation message
strange_device.c:1:10: fatal error: bits/stdc++.h: No such file or directory
#include <bits/stdc++.h>
^~~~~~~~~~~~~~~
compilation terminated.
