#include <bits/stdc++.h>
#define endl "\n"
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
int N;
ll A, B, MOD;
set<pii> s;
ll gcdf(ll a, ll b){
return (b == 0 ? a : gcdf(b, a%b));
}
void upd(ll l, ll r){
auto it = s.upper_bound({l, LLONG_MAX});
vector<pii> rm;
if(it != s.begin()){
it--;
if(it -> second >= r){
return;
}
if(it -> second >= l){
l = it -> first;
rm.push_back(*it);
}
it++;
}
for(; it != s.end(); it++){
if(it -> first > r) break;
l = min(l, it -> first);
r = max(r, it -> second);
rm.push_back(*it);
}
for(pii i : rm){
s.erase(i);
}
s.insert({l, r});
}
int32_t main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> A >> B;
__int128 mp = A / gcdf(A, B+1) * B;
MOD = (mp > 1e18 ? 1e18+5 : (ll)mp);
for(int i = 0; i < N; i++){
ll l, r; cin >> l >> r;
if(r - l + 1 >= MOD){
upd(0, MOD-1);
}
l %= MOD, r %= MOD;
if(l > r){
upd(l, MOD-1);
upd(0, r);
}else{
upd(l, r);
}
}
ll ans = 0;
for(pii i : s){
ans += i.se - i.fi + 1;
}
cout << ans << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
7 ms |
1004 KB |
Output is correct |
3 |
Correct |
7 ms |
1004 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
0 ms |
364 KB |
Output is correct |
6 |
Correct |
0 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 |
0 ms |
364 KB |
Output is correct |
12 |
Correct |
0 ms |
364 KB |
Output is correct |
13 |
Correct |
0 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 |
7 ms |
876 KB |
Output is correct |
17 |
Correct |
76 ms |
6636 KB |
Output is correct |
18 |
Incorrect |
0 ms |
364 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
0 ms |
364 KB |
Output is correct |
4 |
Correct |
0 ms |
364 KB |
Output is correct |
5 |
Incorrect |
0 ms |
364 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
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 |
Correct |
307 ms |
492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
364 KB |
Output is correct |
2 |
Correct |
793 ms |
63084 KB |
Output is correct |
3 |
Correct |
784 ms |
63084 KB |
Output is correct |
4 |
Correct |
872 ms |
63084 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
364 KB |
Output is correct |
2 |
Correct |
793 ms |
63084 KB |
Output is correct |
3 |
Correct |
784 ms |
63084 KB |
Output is correct |
4 |
Correct |
872 ms |
63084 KB |
Output is correct |
5 |
Correct |
0 ms |
364 KB |
Output is correct |
6 |
Correct |
787 ms |
63204 KB |
Output is correct |
7 |
Correct |
799 ms |
63340 KB |
Output is correct |
8 |
Correct |
773 ms |
63028 KB |
Output is correct |
9 |
Correct |
892 ms |
63144 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
364 KB |
Output is correct |
2 |
Correct |
793 ms |
63084 KB |
Output is correct |
3 |
Correct |
784 ms |
63084 KB |
Output is correct |
4 |
Correct |
872 ms |
63084 KB |
Output is correct |
5 |
Correct |
0 ms |
364 KB |
Output is correct |
6 |
Correct |
66 ms |
6508 KB |
Output is correct |
7 |
Correct |
72 ms |
6636 KB |
Output is correct |
8 |
Correct |
69 ms |
6636 KB |
Output is correct |
9 |
Correct |
76 ms |
6636 KB |
Output is correct |
10 |
Correct |
78 ms |
6508 KB |
Output is correct |
11 |
Correct |
68 ms |
6636 KB |
Output is correct |
12 |
Correct |
88 ms |
6528 KB |
Output is correct |
13 |
Correct |
78 ms |
6636 KB |
Output is correct |
14 |
Correct |
71 ms |
6508 KB |
Output is correct |
15 |
Correct |
88 ms |
6764 KB |
Output is correct |
16 |
Correct |
78 ms |
6636 KB |
Output is correct |
17 |
Correct |
79 ms |
6636 KB |
Output is correct |
18 |
Correct |
788 ms |
63212 KB |
Output is correct |
19 |
Correct |
795 ms |
63000 KB |
Output is correct |
20 |
Correct |
822 ms |
63084 KB |
Output is correct |
21 |
Correct |
72 ms |
6636 KB |
Output is correct |
22 |
Correct |
79 ms |
6636 KB |
Output is correct |
23 |
Correct |
128 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
364 KB |
Output is correct |
2 |
Correct |
75 ms |
6508 KB |
Output is correct |
3 |
Correct |
93 ms |
6636 KB |
Output is correct |
4 |
Correct |
810 ms |
62956 KB |
Output is correct |
5 |
Correct |
79 ms |
6636 KB |
Output is correct |
6 |
Correct |
81 ms |
6764 KB |
Output is correct |
7 |
Correct |
80 ms |
6636 KB |
Output is correct |
8 |
Correct |
78 ms |
6636 KB |
Output is correct |
9 |
Correct |
80 ms |
6636 KB |
Output is correct |
10 |
Correct |
71 ms |
6636 KB |
Output is correct |
11 |
Correct |
72 ms |
6636 KB |
Output is correct |
12 |
Correct |
76 ms |
6636 KB |
Output is correct |
13 |
Correct |
78 ms |
6764 KB |
Output is correct |
14 |
Correct |
858 ms |
62952 KB |
Output is correct |
15 |
Correct |
66 ms |
5996 KB |
Output is correct |
16 |
Correct |
777 ms |
63084 KB |
Output is correct |
17 |
Correct |
769 ms |
62956 KB |
Output is correct |
18 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
7 ms |
1004 KB |
Output is correct |
3 |
Correct |
7 ms |
1004 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
0 ms |
364 KB |
Output is correct |
6 |
Correct |
0 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 |
0 ms |
364 KB |
Output is correct |
12 |
Correct |
0 ms |
364 KB |
Output is correct |
13 |
Correct |
0 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 |
7 ms |
876 KB |
Output is correct |
17 |
Correct |
76 ms |
6636 KB |
Output is correct |
18 |
Incorrect |
0 ms |
364 KB |
Output isn't correct |