#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
typedef long long llo;
#define ak first
#define bk second
#define endl "\n"
llo gcd(llo kk,llo ll){
if(ll==0){
return kk;
}
return gcd(ll,kk%ll);
}
const llo inf = (llo)1e18 + 3;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
llo n,a,b;
cin>>n>>a>>b;
llo x;
vector<pair<llo,llo>> it;
x=b;
llo y=a/gcd(a,b+1);
/*if(y>1000000000000000000LL/b){
}*/
/* if((b+1)%a==0){
x=b;
}
else{
x=a*b;
}*/
llo aa,bb;
llo ss=0;
vector<pair<llo,llo>> ac;
for(llo i=0;i<n;i++){
cin>>aa>>bb;
ss+=bb-aa+1;
it.pb(mp(aa,bb));
}
if(y>(llo)2*(inf/b)){
cout<<ss<<endl;
return 0;
}
x*=(a/gcd(a,b+1));
for(llo i=0;i<n;i++){
aa=it[i].ak;
bb=it[i].bk;
if(bb-aa+1>=x){
cout<<x<<endl;
return 0;
}
/*if(bb-aa+1>=x){
ac.pb(mp(0,x-1));
}*/
aa%=x;
bb%=x;
if(bb<aa){
ac.pb(mp(aa,x-1));
ac.pb(mp(0,bb));
}
else{
ac.pb(mp(aa,bb));
}
}
/* if(s==1){
cout<<x<<endl;
}
else{*/
vector<pair<llo,llo>> prev;
sort(ac.begin(),ac.end());
for(auto cc:ac){
if(prev.size()==0){
prev.pb(cc);
}
else{
if(cc.ak>prev[prev.size()-1].bk){
prev.pb(cc);
}
else{
prev[prev.size()-1].bk=max(prev[prev.size()-1].bk,cc.bk);
}
}
}
llo tot=0;
for(llo i=0;i<prev.size();i++){
tot+=prev[i].bk-prev[i].ak+1;
}
/* if(s==1 and tot<x){
while(true){
int y=1;
}
}
*/
cout<<tot<<endl;
//}
return 0;
}
Compilation message
strange_device.cpp: In function 'int main()':
strange_device.cpp:95:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(llo i=0;i<prev.size();i++){
~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
10 ms |
1012 KB |
Output is correct |
3 |
Correct |
11 ms |
1012 KB |
Output is correct |
4 |
Correct |
5 ms |
376 KB |
Output is correct |
5 |
Correct |
5 ms |
376 KB |
Output is correct |
6 |
Correct |
5 ms |
376 KB |
Output is correct |
7 |
Correct |
5 ms |
376 KB |
Output is correct |
8 |
Correct |
5 ms |
376 KB |
Output is correct |
9 |
Correct |
5 ms |
376 KB |
Output is correct |
10 |
Correct |
5 ms |
376 KB |
Output is correct |
11 |
Correct |
5 ms |
376 KB |
Output is correct |
12 |
Correct |
5 ms |
380 KB |
Output is correct |
13 |
Correct |
4 ms |
380 KB |
Output is correct |
14 |
Correct |
5 ms |
376 KB |
Output is correct |
15 |
Correct |
4 ms |
376 KB |
Output is correct |
16 |
Correct |
10 ms |
1012 KB |
Output is correct |
17 |
Correct |
65 ms |
6632 KB |
Output is correct |
18 |
Correct |
5 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
376 KB |
Output is correct |
2 |
Correct |
5 ms |
376 KB |
Output is correct |
3 |
Correct |
5 ms |
376 KB |
Output is correct |
4 |
Correct |
5 ms |
376 KB |
Output is correct |
5 |
Correct |
4 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
5 ms |
376 KB |
Output is correct |
3 |
Correct |
5 ms |
376 KB |
Output is correct |
4 |
Correct |
5 ms |
376 KB |
Output is correct |
5 |
Correct |
419 ms |
40616 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
561 ms |
56264 KB |
Output is correct |
3 |
Correct |
557 ms |
56228 KB |
Output is correct |
4 |
Correct |
551 ms |
56392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
561 ms |
56264 KB |
Output is correct |
3 |
Correct |
557 ms |
56228 KB |
Output is correct |
4 |
Correct |
551 ms |
56392 KB |
Output is correct |
5 |
Correct |
5 ms |
376 KB |
Output is correct |
6 |
Correct |
567 ms |
56360 KB |
Output is correct |
7 |
Correct |
563 ms |
56480 KB |
Output is correct |
8 |
Correct |
571 ms |
56224 KB |
Output is correct |
9 |
Correct |
605 ms |
56484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
561 ms |
56264 KB |
Output is correct |
3 |
Correct |
557 ms |
56228 KB |
Output is correct |
4 |
Correct |
551 ms |
56392 KB |
Output is correct |
5 |
Correct |
4 ms |
376 KB |
Output is correct |
6 |
Correct |
58 ms |
6500 KB |
Output is correct |
7 |
Correct |
62 ms |
6500 KB |
Output is correct |
8 |
Correct |
62 ms |
6504 KB |
Output is correct |
9 |
Correct |
59 ms |
6628 KB |
Output is correct |
10 |
Correct |
59 ms |
6504 KB |
Output is correct |
11 |
Correct |
60 ms |
6500 KB |
Output is correct |
12 |
Correct |
59 ms |
6496 KB |
Output is correct |
13 |
Correct |
61 ms |
6504 KB |
Output is correct |
14 |
Correct |
60 ms |
6500 KB |
Output is correct |
15 |
Correct |
64 ms |
6568 KB |
Output is correct |
16 |
Correct |
63 ms |
6628 KB |
Output is correct |
17 |
Correct |
59 ms |
6500 KB |
Output is correct |
18 |
Correct |
556 ms |
56476 KB |
Output is correct |
19 |
Correct |
565 ms |
56480 KB |
Output is correct |
20 |
Correct |
628 ms |
56448 KB |
Output is correct |
21 |
Correct |
62 ms |
6628 KB |
Output is correct |
22 |
Correct |
57 ms |
6500 KB |
Output is correct |
23 |
Correct |
177 ms |
18000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
63 ms |
6528 KB |
Output is correct |
3 |
Correct |
62 ms |
6496 KB |
Output is correct |
4 |
Correct |
632 ms |
56420 KB |
Output is correct |
5 |
Correct |
62 ms |
6628 KB |
Output is correct |
6 |
Correct |
64 ms |
6592 KB |
Output is correct |
7 |
Correct |
62 ms |
6500 KB |
Output is correct |
8 |
Correct |
64 ms |
6500 KB |
Output is correct |
9 |
Correct |
62 ms |
6500 KB |
Output is correct |
10 |
Correct |
63 ms |
6504 KB |
Output is correct |
11 |
Correct |
62 ms |
6500 KB |
Output is correct |
12 |
Correct |
58 ms |
6500 KB |
Output is correct |
13 |
Correct |
64 ms |
6500 KB |
Output is correct |
14 |
Correct |
612 ms |
56452 KB |
Output is correct |
15 |
Correct |
65 ms |
6628 KB |
Output is correct |
16 |
Correct |
544 ms |
56356 KB |
Output is correct |
17 |
Correct |
558 ms |
56360 KB |
Output is correct |
18 |
Correct |
5 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
10 ms |
1012 KB |
Output is correct |
3 |
Correct |
11 ms |
1012 KB |
Output is correct |
4 |
Correct |
5 ms |
376 KB |
Output is correct |
5 |
Correct |
5 ms |
376 KB |
Output is correct |
6 |
Correct |
5 ms |
376 KB |
Output is correct |
7 |
Correct |
5 ms |
376 KB |
Output is correct |
8 |
Correct |
5 ms |
376 KB |
Output is correct |
9 |
Correct |
5 ms |
376 KB |
Output is correct |
10 |
Correct |
5 ms |
376 KB |
Output is correct |
11 |
Correct |
5 ms |
376 KB |
Output is correct |
12 |
Correct |
5 ms |
380 KB |
Output is correct |
13 |
Correct |
4 ms |
380 KB |
Output is correct |
14 |
Correct |
5 ms |
376 KB |
Output is correct |
15 |
Correct |
4 ms |
376 KB |
Output is correct |
16 |
Correct |
10 ms |
1012 KB |
Output is correct |
17 |
Correct |
65 ms |
6632 KB |
Output is correct |
18 |
Correct |
5 ms |
376 KB |
Output is correct |
19 |
Correct |
6 ms |
376 KB |
Output is correct |
20 |
Correct |
5 ms |
376 KB |
Output is correct |
21 |
Correct |
5 ms |
376 KB |
Output is correct |
22 |
Correct |
5 ms |
376 KB |
Output is correct |
23 |
Correct |
4 ms |
376 KB |
Output is correct |
24 |
Correct |
5 ms |
376 KB |
Output is correct |
25 |
Correct |
5 ms |
376 KB |
Output is correct |
26 |
Correct |
5 ms |
376 KB |
Output is correct |
27 |
Correct |
5 ms |
376 KB |
Output is correct |
28 |
Correct |
419 ms |
40616 KB |
Output is correct |
29 |
Correct |
5 ms |
376 KB |
Output is correct |
30 |
Correct |
561 ms |
56264 KB |
Output is correct |
31 |
Correct |
557 ms |
56228 KB |
Output is correct |
32 |
Correct |
551 ms |
56392 KB |
Output is correct |
33 |
Correct |
5 ms |
376 KB |
Output is correct |
34 |
Correct |
567 ms |
56360 KB |
Output is correct |
35 |
Correct |
563 ms |
56480 KB |
Output is correct |
36 |
Correct |
571 ms |
56224 KB |
Output is correct |
37 |
Correct |
605 ms |
56484 KB |
Output is correct |
38 |
Correct |
4 ms |
376 KB |
Output is correct |
39 |
Correct |
58 ms |
6500 KB |
Output is correct |
40 |
Correct |
62 ms |
6500 KB |
Output is correct |
41 |
Correct |
62 ms |
6504 KB |
Output is correct |
42 |
Correct |
59 ms |
6628 KB |
Output is correct |
43 |
Correct |
59 ms |
6504 KB |
Output is correct |
44 |
Correct |
60 ms |
6500 KB |
Output is correct |
45 |
Correct |
59 ms |
6496 KB |
Output is correct |
46 |
Correct |
61 ms |
6504 KB |
Output is correct |
47 |
Correct |
60 ms |
6500 KB |
Output is correct |
48 |
Correct |
64 ms |
6568 KB |
Output is correct |
49 |
Correct |
63 ms |
6628 KB |
Output is correct |
50 |
Correct |
59 ms |
6500 KB |
Output is correct |
51 |
Correct |
556 ms |
56476 KB |
Output is correct |
52 |
Correct |
565 ms |
56480 KB |
Output is correct |
53 |
Correct |
628 ms |
56448 KB |
Output is correct |
54 |
Correct |
62 ms |
6628 KB |
Output is correct |
55 |
Correct |
57 ms |
6500 KB |
Output is correct |
56 |
Correct |
177 ms |
18000 KB |
Output is correct |
57 |
Correct |
5 ms |
376 KB |
Output is correct |
58 |
Correct |
63 ms |
6528 KB |
Output is correct |
59 |
Correct |
62 ms |
6496 KB |
Output is correct |
60 |
Correct |
632 ms |
56420 KB |
Output is correct |
61 |
Correct |
62 ms |
6628 KB |
Output is correct |
62 |
Correct |
64 ms |
6592 KB |
Output is correct |
63 |
Correct |
62 ms |
6500 KB |
Output is correct |
64 |
Correct |
64 ms |
6500 KB |
Output is correct |
65 |
Correct |
62 ms |
6500 KB |
Output is correct |
66 |
Correct |
63 ms |
6504 KB |
Output is correct |
67 |
Correct |
62 ms |
6500 KB |
Output is correct |
68 |
Correct |
58 ms |
6500 KB |
Output is correct |
69 |
Correct |
64 ms |
6500 KB |
Output is correct |
70 |
Correct |
612 ms |
56452 KB |
Output is correct |
71 |
Correct |
65 ms |
6628 KB |
Output is correct |
72 |
Correct |
544 ms |
56356 KB |
Output is correct |
73 |
Correct |
558 ms |
56360 KB |
Output is correct |
74 |
Correct |
5 ms |
376 KB |
Output is correct |
75 |
Correct |
5 ms |
376 KB |
Output is correct |
76 |
Correct |
5 ms |
376 KB |
Output is correct |
77 |
Correct |
5 ms |
376 KB |
Output is correct |
78 |
Correct |
5 ms |
376 KB |
Output is correct |
79 |
Correct |
11 ms |
1372 KB |
Output is correct |
80 |
Correct |
640 ms |
62932 KB |
Output is correct |
81 |
Correct |
652 ms |
63004 KB |
Output is correct |
82 |
Correct |
622 ms |
62940 KB |
Output is correct |
83 |
Correct |
624 ms |
63024 KB |
Output is correct |
84 |
Correct |
621 ms |
63048 KB |
Output is correct |
85 |
Correct |
633 ms |
63392 KB |
Output is correct |
86 |
Correct |
187 ms |
30548 KB |
Output is correct |
87 |
Correct |
5 ms |
380 KB |
Output is correct |