Submission #712752

#	Time	Username	Problem	Language	Result	Execution time	Memory
712752		HuyQuang_re_Zero	Strange Device (APIO19_strange_device)	C++14	10 / 100	671 ms	68940 KiB

strange_device

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 4000002
#define II pair <ll,ll>
#define fst first
#define snd second
using namespace std;
ll n,a,b,l,r,m,i;
II c[N];
void sub1()
{
    ll res=0;
    for(i=1;i<=n;i++) cin>>l>>r,res+=(r-l+1);
    cout<<res;
}
void add(ll l,ll r) { c[++m]={ l,1 }; c[++m]={ r,-1 }; }
void sub2()
{
    for(i=1;i<=n;i++)
    {
        cin>>l>>r;
        if(r-l+1>=a*b) { cout<<a*b; return ; }
        l=l%(a*b); r=r%(a*b);
        if(l<=r) add(l,r);
        else add(l,a*b-1),add(0,r);
    }
    sort(c+1,c+m+1);
    c[0]={ -1,1 };
    ll cnt=0,res=0;
    for(i=1;i<=m;i++)
    {
        if(c[i].fst>c[i-1].fst)
        {
            if(cnt>0) res+=c[i].fst-c[i-1].fst;
            else res++;
        }
        cnt+=c[i].snd;
    }
    cout<<res;
}
int main()
{
   // freopen("ntu.inp","r",stdin);
    //freopen("ntu.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>a>>b;
    if(b>round(1e18)/a) sub1();
    else sub2();
}

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