Submission #712888

#	Time	Username	Problem	Language	Result	Execution time	Memory
712888		HuyQuang_re_Zero	Strange Device (APIO19_strange_device)	C++14	100 / 100	586 ms	68956 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,x;
II c[N];
void add(ll l,ll r) { c[++m]={ l,1 }; c[++m]={ r,-1 }; }
const ll oo=round(1e18);
ll cal()
{
    ll bb=(b%a+1)%a,x=a/__gcd(bb,a);
    if(x>oo/b) return oo+1;
    return x*b;
}
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;
    x=cal();
    for(i=1;i<=n;i++)
    {
        cin>>l>>r;
        if(r-l+1>=x) { cout<<x; return 0; }
        l=l%x; r=r%x;
        if(l<=r) add(l,r);
        else add(l,x-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;
}

• 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