#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define INF 1e9+7
#define all(x) x.begin(),x.end()
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using pii=pair<int,int>;
using ppi=pair<int,pii>;
using oset=tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;
template<typename T>
void _print(vector<T> x) {cerr<<"{"; for(auto e:x) cerr<<e<<","; cerr<<"}";}
void _print(pii x) {cerr<<"{"<<x.first<<","<<x.second<<"}";}
template<typename T>
void _print(T x) {cerr<<x;}
void dbg() {cerr<<endl;}
template<typename Head,typename... Tail>
void dbg(Head H,Tail... T) {
_print(H);
if(sizeof...(T)) cerr<<",";
else cerr<<"\"]";
dbg(T...);
}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:[\"",dbg(__VA_ARGS__)
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using pll=pair<ll,ll>;
int main () {
ios::sync_with_stdio(false); cin.tie(0);
ll n,a,b; cin>>n>>a>>b;
vector<pll> seg;
if(a&1) {
for(int tt=0;tt<n;tt++) {
ll l,r; cin>>l>>r;
l%=a; r%=a;
if(l<=r) seg.push_back({l,r});
else {
seg.push_back({0,r});
seg.push_back({l,a-1});
}
}
sort(all(seg));
ll L=seg[0].first,R=seg[0].second;
int len=seg.size();
ll ans=0;
for(int i=1;i<len;i++) {
if(seg[i].first<=R) {
R=max(R,seg[i].second);
}
else {
ans+=(R-L)+1;
L=seg[i].first;
R=seg[i].second;
}
}
ans+=(R-L)+1;
cout<<ans<<endl;
}
else {
for(int tt=0;tt<n;tt++) {
ll l,r; cin>>l>>r;
l=(l*2)%a,r=(r*2)%a;
if(l<=r) seg.push_back({l,r});
else {
seg.push_back({0,r});
if(l<=a-2) seg.push_back({l,a-2});
}
}
sort(all(seg));
ll L=seg[0].first,R=seg[0].second;
ll ans=0;
int len=seg.size();
for(int i=1;i<len;i++) {
if(seg[i].first<=R) {
R=max(R,seg[i].second);
}
else {
ans+=(R-L)/2+1;
L=seg[i].first,R=seg[i].second;
}
}
ans+=(R-L)/2+1;
cout<<ans<<endl;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Incorrect |
5 ms |
592 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 |
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 |
Incorrect |
1 ms |
332 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 |
452 ms |
16780 KB |
Output is correct |
3 |
Correct |
451 ms |
30300 KB |
Output is correct |
4 |
Correct |
432 ms |
30224 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
452 ms |
16780 KB |
Output is correct |
3 |
Correct |
451 ms |
30300 KB |
Output is correct |
4 |
Correct |
432 ms |
30224 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Incorrect |
491 ms |
30212 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
452 ms |
16780 KB |
Output is correct |
3 |
Correct |
451 ms |
30300 KB |
Output is correct |
4 |
Correct |
432 ms |
30224 KB |
Output is correct |
5 |
Correct |
1 ms |
208 KB |
Output is correct |
6 |
Incorrect |
46 ms |
5692 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Incorrect |
49 ms |
5720 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 |
Incorrect |
5 ms |
592 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |