Submission #938939

#	Time	Username	Problem	Language	Result	Execution time	Memory
938939		Andreibatman	Strange Device (APIO19_strange_device)	C++14	100 / 100	430 ms	54664 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;
long long n,a,b,ans,i,t,k,pozst,lg,schema,ok,st,dr,x;
struct ceva
{
    long long l,r;
}v[5000010];
bool cmp(ceva a,ceva b)
{
    return a.l<b.l || (a.l==b.l && a.r<b.r);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>a>>b;
    b++;
    x=__gcd(a,b);
    a=a/x;
    if(ULLONG_MAX/b<a)
        k=1e18;
    else
        k=a*b;
    k=k-a;
    for(i=1;i<=n;i++)
    {
        cin>>v[i].l>>v[i].r;
        if(v[i].r-v[i].l+1>=k)
        {
            cout<<k;
            return 0;
        }
        v[i].l%=k;
        v[i].r%=k;
        if(v[i].l<=v[i].r)
            ;
        else
        {
            v[n+(++schema)]={v[i].l,k-1};
            v[i]={0,v[i].r};
        }
    }
    n=n+schema;
    sort(v+1,v+n+1,cmp);
    //for(i=1;i<=n;i++)
    //    cout<<v[i].l<<" "<<v[i].r<<'\n';
    st=-1;
    dr=0;
    for(i=1;i<=n;i++)
    {
        if(v[i].r<=st)
            continue;
        ans=ans+v[i].r-max(v[i].l-1,st);
        st=v[i].r;
    }
    cout<<ans;
    return 0;
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:21:20: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'long long int' [-Wsign-compare]
   21 |     if(ULLONG_MAX/b<a)
      |                    ^

• 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