/*
Editor: Abdelrahman Hossam
Nickname: Blobo2_Blobo2
IOI next year isA :)
*/
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
#define all(v) v.begin(),v.end()
#define gen(arr,n,nxt) generate(arr,arr+n,nxt)
#define base ios_base::sync_with_stdio(false);cin.tie(0);
using namespace std;
const int mo=1e9+7;
int nxt(){int x;cin>>x;return x;}
signed main(){
base
int n=nxt(),a=nxt(),b=nxt();
a/=__gcd(a,b+1);
int x=1000000000000000001;
vector<pair<int,int> >v;
if(a<=LLONG_MAX/b)
x=a*b;
bool flag=0;
for(int i=0;i<n;i++){
int first=nxt(),sec=nxt();
if(sec-first+1==x)flag=1;
else if(sec%x<first%x){
first%=x;
sec%=x;
v.push_back({first,x-1});
v.push_back({0,sec});
}
else v.push_back({first%x,sec%x});
}
if(flag){
cout<<x<<endl;
return 0;
}
sort(all(v));
int cnt=0,l=v[0].first,r=v[0].second;
for(int i=0;i<v.size();i++){
if(v[i].first<=r)r=max(r,v[i].second);
else{
cnt+=r-l+1;
r=v[i].second;
l=v[i].first;
}
}
cnt+=r-l+1;
cout<<cnt<<endl;
return 0;
}
Compilation message
strange_device.cpp: In function 'int main()':
strange_device.cpp:46:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for(int i=0;i<v.size();i++){
| ~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
5 ms |
592 KB |
Output is correct |
3 |
Correct |
6 ms |
960 KB |
Output is correct |
4 |
Correct |
1 ms |
316 KB |
Output is correct |
5 |
Correct |
1 ms |
312 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
5 ms |
968 KB |
Output is correct |
17 |
Correct |
54 ms |
5640 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
373 ms |
16832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
496 ms |
16760 KB |
Output is correct |
3 |
Correct |
478 ms |
28752 KB |
Output is correct |
4 |
Correct |
474 ms |
31396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
496 ms |
16760 KB |
Output is correct |
3 |
Correct |
478 ms |
28752 KB |
Output is correct |
4 |
Correct |
474 ms |
31396 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
489 ms |
30744 KB |
Output is correct |
7 |
Correct |
529 ms |
29520 KB |
Output is correct |
8 |
Correct |
475 ms |
29936 KB |
Output is correct |
9 |
Correct |
523 ms |
29424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
496 ms |
16760 KB |
Output is correct |
3 |
Correct |
478 ms |
28752 KB |
Output is correct |
4 |
Correct |
474 ms |
31396 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
48 ms |
5628 KB |
Output is correct |
7 |
Correct |
51 ms |
5656 KB |
Output is correct |
8 |
Correct |
48 ms |
5596 KB |
Output is correct |
9 |
Correct |
47 ms |
5632 KB |
Output is correct |
10 |
Correct |
50 ms |
5688 KB |
Output is correct |
11 |
Correct |
50 ms |
5692 KB |
Output is correct |
12 |
Correct |
47 ms |
5656 KB |
Output is correct |
13 |
Correct |
61 ms |
5688 KB |
Output is correct |
14 |
Correct |
48 ms |
5636 KB |
Output is correct |
15 |
Correct |
52 ms |
5604 KB |
Output is correct |
16 |
Correct |
53 ms |
5692 KB |
Output is correct |
17 |
Correct |
51 ms |
5736 KB |
Output is correct |
18 |
Correct |
513 ms |
29456 KB |
Output is correct |
19 |
Correct |
471 ms |
29424 KB |
Output is correct |
20 |
Correct |
522 ms |
29588 KB |
Output is correct |
21 |
Correct |
51 ms |
5616 KB |
Output is correct |
22 |
Correct |
45 ms |
5672 KB |
Output is correct |
23 |
Correct |
159 ms |
16428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
51 ms |
2476 KB |
Output is correct |
3 |
Correct |
50 ms |
2504 KB |
Output is correct |
4 |
Correct |
552 ms |
16796 KB |
Output is correct |
5 |
Correct |
49 ms |
2408 KB |
Output is correct |
6 |
Correct |
48 ms |
2408 KB |
Output is correct |
7 |
Correct |
49 ms |
2432 KB |
Output is correct |
8 |
Correct |
51 ms |
2496 KB |
Output is correct |
9 |
Correct |
49 ms |
2496 KB |
Output is correct |
10 |
Correct |
51 ms |
2468 KB |
Output is correct |
11 |
Correct |
50 ms |
2416 KB |
Output is correct |
12 |
Correct |
44 ms |
2496 KB |
Output is correct |
13 |
Correct |
51 ms |
2432 KB |
Output is correct |
14 |
Correct |
521 ms |
16780 KB |
Output is correct |
15 |
Correct |
51 ms |
2404 KB |
Output is correct |
16 |
Correct |
464 ms |
16828 KB |
Output is correct |
17 |
Correct |
459 ms |
16848 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
5 ms |
592 KB |
Output is correct |
3 |
Correct |
6 ms |
960 KB |
Output is correct |
4 |
Correct |
1 ms |
316 KB |
Output is correct |
5 |
Correct |
1 ms |
312 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
5 ms |
968 KB |
Output is correct |
17 |
Correct |
54 ms |
5640 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
21 |
Halted |
0 ms |
0 KB |
- |