#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define pll pair<ll , ll >
#define all(x) (x).begin(),(x).end()
#define SZ(x) (ll)(x).size()
#define X first
#define Y second
#define mp make_pair
#define pii pair<int , int>
#define vec vector
#define file_io freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
ll poww(ll a, ll b, ll md) {
return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}
ll gcd(ll a, ll b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
const int maxn = 1000*1000+5 ;
const ll inf = 4223372036854775807 ;
const ll mod = 1e9 + 7 ;
const int lg = 20 ;
ll n , a , b , l , r , L , R , ans , p , w, k ;
set<pll> s ;
int main()
{
migmig ;
cin>>n>>a>>b ;
if(a/gcd(a , b + 1) > inf / b) p = inf ;
else p = a / gcd(a , b + 1) * b ;
cout<<"p : " << p << endl ;
while(n--){
cin>>l>>r ;
if(k) continue ;
if(r - l + 1 >= p ){
k = 1 ;
ans = p ;
continue ;
}
l = l % p ;
r = r % p ;
// cout<<n <<" : " << endl ;
if(r >= l){
s.insert({l , r}) ;
// cout<<l<<","<<r << endl ;
}else{
s.insert({0 , r}) ;
s.insert({l , p - 1}) ;
// cout<<0 <<","<<r <<" & " <<l <<","<<p-1 << endl ;
}
}
if(k){
cout<<ans ;
return 0;
}
s.insert({inf + 1 , inf + 1}) ;
L = s.begin() -> X , R = s.begin() -> Y ;
auto it = next(s.begin()) ;
while(it != s.end()){
if(it -> X > R){
ans += R - L + 1 ;
//cout<<" ad " << L <<" , " << R << endl ;
L = it -> X , R = it -> Y ;
}else{
R = max(R , it -> Y) ;
}
it++ ;
}
cout<<ans << endl ;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
