#include<bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define vll vector<ll>
using namespace std;
vll val,vval;int sz;
vector<pll>t;
vector<ll>lz;
void build(int i,int l,int r){
if(l==r)return void(t[i]={0,vval[l]-vval[l-1]});
int m=(l+r)>>1;build(2*i,l,m);build(2*i+1,m+1,r);
t[i]={0,r-l+1};
}
void push(int i,int l,int r){
t[i].f+=lz[i];
if(l<r)lz[2*i]+=lz[i],lz[2*i+1]+=lz[i];
lz[i]=0;
}
void upd(int i,int l,int r,int tl,int tr,ll v){
push(i,l,r);
if(r<tl||l>tr)return;
if(r<=tr&&l>=tl){
lz[i]+=v;push(i,l,r);return;
}int m=(l+r)>>1;upd(2*i,l,m,tl,tr,v);upd(2*i+1,m+1,r,tl,tr,v);
if(t[2*i].f==t[2*i+1].f)t[i]={t[2*i].f,t[2*i].s+t[2*i+1].s};
else t[i]=min(t[2*i],t[2*i+1]);
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
ll n,a,b,d;cin>>n>>a>>b;d=a/__gcd(a,b+1);val.pb(0);val.pb(d);
ll ans=0;vector<pair<ll,pll>>v;
for(int i=0;i<n;i++){
ll l,r;cin>>l>>r;ans+=r-l+1;
ll x=l/b,y=r/b,z=l%b,tt=r%b;
if(z<=tt){
if(0<=z-1&&x+1<=y)v.pb({0,{x+1,y}}),v.pb({z,{-x-1,-y}}),val.pb((x+1)%d),val.pb((y)%d+1);
if(z<=tt&&x<=y)v.pb({z,{x,y}}),v.pb({tt+1,{-x,-y}}),val.pb(x%d),val.pb((y)%d+1);
if(tt+1<=b-1&&x<=y-1)v.pb({tt+1,{x,y-1}}),v.pb({b,{-x,-y+1}}),val.pb(x%d),val.pb((y-1+d)%d+1);
}
else {
if(0<=tt&&x+1<=y)v.pb({0,{x+1,y}}),v.pb({tt+1,{-x-1,-y}}),val.pb((x+1)%d),val.pb((y)%d+1);
if(tt+1<=z-1&&x+1<=y-1)v.pb({tt+1,{x+1,y-1}}),v.pb({z,{-x-1,-y+1}}),val.pb((x+1)%d),val.pb((y-1+d)%d+1);
if(z<=b-1&&x<=y-1)v.pb({z,{x,y-1}}),v.pb({b,{-x,-y+1}}),val.pb(x%d),val.pb((y-1+d)%d+1);
}
}sort(v.begin(),v.end());sort(val.begin(),val.end());val.erase(unique(val.begin(),val.end()),val.end());vval=val;vval.pb(d);
sz=(int)val.size();t.resize(4*((int)val.size()+1)),lz.resize(4*((int)val.size()+1),0);build(1,1,sz);
for(int i=0;i<v.size()-1;i++){
ll x=abs(v[i].s.f)/d,y=abs(v[i].s.s)/d,z=abs(v[i].s.f)%d,tt=abs(v[i].s.s)%d;
ll add=y-x+1;
if(v[i].s.f>=0&&v[i].s.s>=0){
if(z<=tt){
int tl,tr;
tl = upper_bound(val.begin(),val.end(),0)-val.begin();
tr = upper_bound(val.begin(),val.end(),z)-val.begin();
upd(1,1,sz,tl,tr-1,add-1);
tl = upper_bound(val.begin(),val.end(),z)-val.begin();
tr = upper_bound(val.begin(),val.end(),tt+1)-val.begin();
upd(1,1,sz,tl,tr-1,add);
tl = upper_bound(val.begin(),val.end(),tt+1)-val.begin();
tr = upper_bound(val.begin(),val.end(),d)-val.begin();
upd(1,1,sz,tl,tr-1,add-1);
}
else {
int tl,tr;
tl = upper_bound(val.begin(),val.end(),0)-val.begin();
tr = upper_bound(val.begin(),val.end(),tt+1)-val.begin();
upd(1,1,sz,tl,tr-1,add-1);
tl = upper_bound(val.begin(),val.end(),tt+1)-val.begin();
tr = upper_bound(val.begin(),val.end(),z)-val.begin();
upd(1,1,sz,tl,tr-1,add-2);
tl = upper_bound(val.begin(),val.end(),z)-val.begin();
tr = upper_bound(val.begin(),val.end(),d)-val.begin();
upd(1,1,sz,tl,tr-1,add-1);
}
}
else {
if(z<=tt){
int tl,tr;
tl = upper_bound(val.begin(),val.end(),0)-val.begin();
tr = upper_bound(val.begin(),val.end(),z)-val.begin();
upd(1,1,sz,tl,tr-1,-add+1);
tl = upper_bound(val.begin(),val.end(),z)-val.begin();
tr = upper_bound(val.begin(),val.end(),tt+1)-val.begin();
upd(1,1,sz,tl,tr-1,-add);
tl = upper_bound(val.begin(),val.end(),tt+1)-val.begin();
tr = upper_bound(val.begin(),val.end(),d)-val.begin();
upd(1,1,sz,tl,tr-1,-add+1);
}
else {
int tl,tr;
tl = upper_bound(val.begin(),val.end(),0)-val.begin();
tr = upper_bound(val.begin(),val.end(),tt+1)-val.begin();
upd(1,1,sz,tl,tr-1,-add+1);
tl = upper_bound(val.begin(),val.end(),tt+1)-val.begin();
tr = upper_bound(val.begin(),val.end(),z)-val.begin();
upd(1,1,sz,tl,tr-1,-add+2);
tl = upper_bound(val.begin(),val.end(),z)-val.begin();
tr = upper_bound(val.begin(),val.end(),d)-val.begin();
upd(1,1,sz,tl,tr-1,-add+1);
}
}
if(t[1].s==0)ans+=(v[i+1].f-v[i].f)*t[1].s;
}cout<<ans;
}
Compilation message
strange_device.cpp: In function 'int main()':
strange_device.cpp:55:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for(int i=0;i<v.size()-1;i++){
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
1396 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
984 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
2962 ms |
174736 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
2962 ms |
174736 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
2962 ms |
174736 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
161 ms |
9532 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
1396 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
