#include<bits/stdc++.h>
using namespace std;
#define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll
int n, a, b;
int gcd(int x, int y){
int a=x, b=y;
if(a<b){
swap(a, b);
}
if(b==0){return a;}
return gcd(b, a%b);
}
int32_t main(){
INIT
cin>>n>>a>>b;
int k=a/gcd(a, b+1);
int m=k*b;
//cout<<(m)<<"\n";
set<pii> s;
int l, r;
for(int i=1; i<=n; i++){
cin>>l>>r;
s.insert( {(l%m), min(m-1, (l%m)+r-l )} );
if( (r-l+1)>=m ){
cout<<m<<"\n";
for(int j=i+1; j<=n; j++){
cin>>l>>r;
}
return 0;
}
if( r>(l+(m-1-l%m) ) ){
s.insert({0, r%m});
}
}
l=0, r=-1;
int res=0;
for(auto it=s.begin(); it!=s.end(); it++){
//cout<<l<<" "<<r<<"\n";
if(r==-1){
r=it->sc; l=it->ft;
continue;
}
if(it->ft>r){
res+=(r-l+1);
l=it->ft, r=it->sc;
continue;
}
r=max(r, it->sc);
}
//cout<<l<<" "<<r<<"\n";
res+=(r-l+1);
cout<<res;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
9 ms |
1388 KB |
Output is correct |
3 |
Correct |
9 ms |
1388 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
6 ms |
1388 KB |
Output is correct |
17 |
Correct |
65 ms |
9836 KB |
Output is correct |
18 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
492 KB |
Output is correct |
3 |
Correct |
1 ms |
492 KB |
Output is correct |
4 |
Correct |
1 ms |
492 KB |
Output is correct |
5 |
Correct |
305 ms |
7788 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
684 ms |
63304 KB |
Output is correct |
3 |
Correct |
678 ms |
67308 KB |
Output is correct |
4 |
Correct |
702 ms |
64820 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
684 ms |
63304 KB |
Output is correct |
3 |
Correct |
678 ms |
67308 KB |
Output is correct |
4 |
Correct |
702 ms |
64820 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
694 ms |
64992 KB |
Output is correct |
7 |
Correct |
670 ms |
64664 KB |
Output is correct |
8 |
Correct |
661 ms |
64748 KB |
Output is correct |
9 |
Correct |
717 ms |
65004 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
684 ms |
63304 KB |
Output is correct |
3 |
Correct |
678 ms |
67308 KB |
Output is correct |
4 |
Correct |
702 ms |
64820 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
70 ms |
8300 KB |
Output is correct |
7 |
Correct |
69 ms |
8300 KB |
Output is correct |
8 |
Correct |
73 ms |
8300 KB |
Output is correct |
9 |
Correct |
69 ms |
8556 KB |
Output is correct |
10 |
Correct |
64 ms |
8428 KB |
Output is correct |
11 |
Correct |
61 ms |
8300 KB |
Output is correct |
12 |
Correct |
63 ms |
8300 KB |
Output is correct |
13 |
Correct |
70 ms |
8300 KB |
Output is correct |
14 |
Correct |
62 ms |
8300 KB |
Output is correct |
15 |
Correct |
69 ms |
8300 KB |
Output is correct |
16 |
Correct |
65 ms |
8300 KB |
Output is correct |
17 |
Correct |
66 ms |
8300 KB |
Output is correct |
18 |
Correct |
704 ms |
65900 KB |
Output is correct |
19 |
Correct |
664 ms |
66540 KB |
Output is correct |
20 |
Correct |
768 ms |
65732 KB |
Output is correct |
21 |
Correct |
64 ms |
8300 KB |
Output is correct |
22 |
Correct |
63 ms |
8300 KB |
Output is correct |
23 |
Correct |
126 ms |
3948 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
71 ms |
9452 KB |
Output is correct |
3 |
Correct |
67 ms |
9324 KB |
Output is correct |
4 |
Correct |
695 ms |
67296 KB |
Output is correct |
5 |
Correct |
64 ms |
8300 KB |
Output is correct |
6 |
Correct |
66 ms |
8428 KB |
Output is correct |
7 |
Correct |
70 ms |
8300 KB |
Output is correct |
8 |
Correct |
75 ms |
8300 KB |
Output is correct |
9 |
Correct |
64 ms |
8300 KB |
Output is correct |
10 |
Correct |
63 ms |
8300 KB |
Output is correct |
11 |
Correct |
65 ms |
8344 KB |
Output is correct |
12 |
Correct |
64 ms |
8300 KB |
Output is correct |
13 |
Correct |
67 ms |
8300 KB |
Output is correct |
14 |
Correct |
683 ms |
66796 KB |
Output is correct |
15 |
Correct |
63 ms |
8300 KB |
Output is correct |
16 |
Correct |
655 ms |
66028 KB |
Output is correct |
17 |
Correct |
658 ms |
66284 KB |
Output is correct |
18 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
9 ms |
1388 KB |
Output is correct |
3 |
Correct |
9 ms |
1388 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
6 ms |
1388 KB |
Output is correct |
17 |
Correct |
65 ms |
9836 KB |
Output is correct |
18 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |