This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using lli = long long;
const lli INF = 2e18;
lli mul(lli a,lli b) {
if(a>=INF || b>=INF || INF/a<b) return INF;
else return min(INF, a*b);
}
int main() {
int n;
lli A,B;
scanf("%d%lld%lld",&n,&A,&B);
lli g = __gcd(A-1,B), s = abs(B-A+1) / g;
lli kg = __gcd(s, A), k = A / kg;
//lli I = mul(k, B/g);
lli I = mul(mul(k, B/g), g);
vector<pair<lli,int>> arr;
for(int i=0;i<n;i++) {
lli l,r;
scanf("%lld%lld",&l,&r);
if(r-l+1>=I) {
arr.push_back({0,1});
arr.push_back({I,-1});
} else {
l%=I; r%=I;
if(l<=r) {
arr.push_back({l,1});
arr.push_back({r+1,-1});
} else {
arr.push_back({0,1});
arr.push_back({r+1,-1});
arr.push_back({l,1});
arr.push_back({I,-1});
}
}
}
lli ans=0,ad=0,pr=0;
sort(arr.begin(),arr.end());
for(int i=0,j=0;i<(int)arr.size();i=j) {
ans += (arr[i].first - pr) * min(ad, 1ll);
for(j=i;j<(int)arr.size() && arr[i].first==arr[j].first;j++) {
ad += arr[j].second;
}
pr = arr[i].first;
}
printf("%lld\n",ans);
return 0;
}
Compilation message (stderr)
strange_device.cpp: In function 'int main()':
strange_device.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%lld%lld",&n,&A,&B);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld",&l,&r);
~~~~~^~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |