Submission #347842

#	Time	Username	Problem	Language	Result	Execution time	Memory
347842		denkendoemeer	Strange Device (APIO19_strange_device)	C++14	25 / 100	574 ms	41396 KiB

strange_device

#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<pair<ll,ll>>v;
ll gcd(ll a,ll b)
{
    ll r=0;
    while(b){
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    ll n,a,b,g,i,x,y,ans=0;
    scanf("%lld%lld%lld",&n,&a,&b);
    g=gcd(a,b+1);
    if ((double)a/g*b>1e17){
        for(i=1;i<=n;i++)
            scanf("%lld%lld",&x,&y),ans=ans+y-x+1;
        printf("%lld\n",ans);
        return 0;
    }
    ll aux=a/g*b;
    for(i=1;i<=n;i++){
        scanf("%lld%lld",&x,&y);
        if (y-x+1>=aux){
            printf("%lld\n",aux);
            return 0;
        }
        x=x%aux;
        y=y%aux;
        if (x>y){
            v.push_back(make_pair(x,aux-1));
            v.push_back(make_pair(0,y));
        }
        else
            v.push_back(make_pair(x,y));
    }
    sort(v.begin(),v.end());
    ll last=-1;
    for(auto it:v){
        ans=ans+max(0LL,it.second-max(last,it.first-1));
        last=max(last,it.second);
    }
    printf("%lld\n",min(ans,aux));
return 0;
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   20 |     scanf("%lld%lld%lld",&n,&a,&b);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:24:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |             scanf("%lld%lld",&x,&y),ans=ans+y-x+1;
      |             ~~~~~^~~~~~~~~~~~~~~~~~
strange_device.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   30 |         scanf("%lld%lld",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~

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