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;
#define int long long
int gcd(int x, int y)
{
while(x>0)
{
int r = y%x;
y=x;
x=r;
}
return y;
}
set<pair<__int128,__int128>> s;
void baga(__int128 le, __int128 ri)
{
if(s.empty())
{
s.insert({le,ri});
return;
}
auto it = s.lower_bound({le+1,-1});
if(it!=s.begin()) it--;
while(it!=s.end())
{
if((*it).first > ri)
break;
if((*it).second < le)
{
it++;
}
else if((*it).first <= le && (*it).second >= ri)
{
return;
}
else
{
le = min(le, (*it).first);
ri = max(ri, (*it).second);
it = s.erase(it);
}
}
s.insert({le,ri});
}
signed main()
{
int n,A,B;
cin>>n>>A>>B;
A = A / gcd(A,B+1);
__int128 le,ri;
__int128 copA=A,copB=B;
__int128 prod=copA*copB;
int cle,cri;
for(int i=1;i<=n;i++)
{
cin>>cle>>cri;
le=cle;
ri=cri;
if(le==ri)
{
baga(le%prod,le%prod);
continue;
}
le = le%prod;
ri = ri%prod;
if(le<ri)
{
baga(le,ri);
}
else
{
baga(le,prod-1);
baga(0,ri);
}
}
int cnt=0;
for(auto it:s)
{
cnt += it.second-it.first+1;
}
cout<<cnt;
return 0;
}
# | 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... |