Submission #252085

#	Time	Username	Problem	Language	Result	Execution time	Memory
252085		jeqcho	Strange Device (APIO19_strange_device)	C++17	100 / 100	1146 ms	148336 KiB

strange_device

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
#define ll long long
#define MAX 1000100
inline ll read()
{
    ll x=0;bool t=false;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=true,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return t?-x:x;
}
ll n,sum,l[MAX],r[MAX],A,B,d,T,ans;
multiset<pair<ll,int> >S;
#define mp make_pair
void Add(ll l,ll r){S.insert(mp(l,1));S.insert(mp(r+1,-1));}
int main()
{
    n=read();A=read();B=read();d=__gcd(A,B+1);
    for(int i=1;i<=n;++i)l[i]=read(),r[i]=read(),sum+=r[i]-l[i]+1;
    if(1.0*A*B/d>1e18){printf("%lld\n",sum);return 0;}
    T=A/d*B;
    for(int i=1;i<=n;++i)
    {
        if(r[i]-l[i]+1>=T){printf("%lld\n",T);return 0;}
        if(l[i]/T!=r[i]/T)Add(l[i]%T,T-1),Add(0,r[i]%T);
        else Add(l[i]%T,r[i]%T);
    }
    S.insert(mp(T,0));
    ll lst=-1,c=0;
    for(auto a:S)
    {
        if(c>0)ans+=a.first-lst;
        c+=a.second;
        lst=a.first;
    }
    printf("%lld\n",ans);
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20
• Subtask 8: 30 / 30