#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const ll N=1e7+7;
struct Node{
ll l;
ll r;
ll vl=-1;
ll vr=-1;
ll val=0;
};
Node tree[N];
ll K;
ll GCD(ll x, ll y){
while(x*y!=0){
if(x>y) x%=y;
else y%=x;
}
return x+y;
}
void update(ll v, ll ql, ll qr){
// cout<<v<<" "<<ql<<" "<<qr<<" "<<tree[v].l<<" "<<tree[v].r<<" "<<tree[v].val<<endl;
if(tree[v].val==tree[v].r-tree[v].l+1){
return;
}
if(qr<tree[v].l && tree[v].r<ql){
return;
}
if(ql<=tree[v].l && tree[v].r<=qr){
tree[v].val=tree[v].r-tree[v].l+1;
return;
}
ll mid=(tree[v].l+tree[v].r)/2;
if(qr<=mid){
if(tree[v].vl==-1){
K++;
tree[v].vl=K;
tree[tree[v].vl].l=tree[v].l;
tree[tree[v].vl].r=mid;
update(tree[v].vl, ql, qr);
}
else if(tree[tree[v].vl].val!=mid-tree[v].l+1){
update(tree[v].vl, ql, qr);
}
}
else if(mid+1<=ql){
if(tree[v].vr==-1){
K++;
tree[v].vr=K;
tree[tree[v].vr].l=mid+1;
tree[tree[v].vr].r=tree[v].r;
update(tree[v].vr, ql, qr);
}
else if(tree[tree[v].vl].val!=tree[v].r-mid){
update(tree[v].vr, ql, qr);
}
}
else{
if(tree[v].vl==-1){
K++;
tree[v].vl=K;
tree[tree[v].vl].l=tree[v].l;
tree[tree[v].vl].r=mid;
update(tree[v].vl, ql, qr);
}
else if(tree[tree[v].vl].val!=mid-tree[v].l+1){
update(tree[v].vl, ql, qr);
}
if(tree[v].vr==-1){
K++;
tree[v].vr=K;
tree[tree[v].vr].l=mid+1;
tree[tree[v].vr].r=tree[v].r;
update(tree[v].vr, ql, qr);
}
else if(tree[tree[v].vl].val!=tree[v].r-mid){
update(tree[v].vr, ql, qr);
}
}
tree[v].val=tree[tree[v].vl].val+tree[tree[v].vr].val;
}
ll query(ll v, ll l, ll r){
return tree[v].val;
}
int main(){
ll n, i, A, B, l, r, k, m, ma;
scanf("%lld",&n);
scanf("%lld",&A);
scanf("%lld",&B);
m=GCD(B+1, A);
A/=m;
ma=1e18+1;
if(ma/A<B){
k=ma;
}
else{
k=A*B;
}
// cout<<k<<endl;
tree[0].l=0;
tree[0].r=k-1;
K=0;
for(i=1; i<=n; i++){
scanf("%lld",&l);
scanf("%lld",&r);
if(r-l+1>=k) update(0, 0, k-1);
else{
if(l%k<=r%k){
update(0, l%k, r%k);
}
else{
update(0, l%k, k-1);
update(0, 0, r%k);
}
}
}
printf("%lld\n", query(0, 0, k-1));
return 0;
}
Compilation message
strange_device.cpp: In function 'int main()':
strange_device.cpp:98:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
98 | scanf("%lld",&n);
| ~~~~~^~~~~~~~~~~
strange_device.cpp:99:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
99 | scanf("%lld",&A);
| ~~~~~^~~~~~~~~~~
strange_device.cpp:100:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
100 | scanf("%lld",&B);
| ~~~~~^~~~~~~~~~~
strange_device.cpp:117:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
117 | scanf("%lld",&l);
| ~~~~~^~~~~~~~~~~
strange_device.cpp:118:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
118 | scanf("%lld",&r);
| ~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
181 ms |
391768 KB |
Output is correct |
| 2 |
Incorrect |
111 ms |
392020 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
103 ms |
391668 KB |
Output is correct |
| 2 |
Correct |
106 ms |
391760 KB |
Output is correct |
| 3 |
Correct |
104 ms |
391684 KB |
Output is correct |
| 4 |
Correct |
104 ms |
391652 KB |
Output is correct |
| 5 |
Correct |
104 ms |
391652 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
105 ms |
391816 KB |
Output is correct |
| 2 |
Incorrect |
107 ms |
391760 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
109 ms |
391652 KB |
Output is correct |
| 2 |
Incorrect |
576 ms |
429008 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
109 ms |
391652 KB |
Output is correct |
| 2 |
Incorrect |
576 ms |
429008 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
109 ms |
391652 KB |
Output is correct |
| 2 |
Incorrect |
576 ms |
429008 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
113 ms |
391800 KB |
Output is correct |
| 2 |
Incorrect |
161 ms |
395428 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
181 ms |
391768 KB |
Output is correct |
| 2 |
Incorrect |
111 ms |
392020 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
