Submission #432641

#	Time	Username	Problem	Language	Result	Execution time	Memory
432641		TLP39	이상한 기계 (APIO19_strange_device)	C++14	100 / 100	737 ms	69804 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pll;

const ll HIGH=1000000000000000000;
ll gcd(ll x,ll y)
{
    if(!x || !y) return x+y;
    return gcd(y,x%y);
}

int n;
ll a,b,c,d;
ll res=0;
ll l,r;
pll t[2000004];
vector<pll> v;
int cou=0;
int main()
{
    scanf("%d %lld %lld",&n,&a,&b);
    c=gcd(a,b+1);
    if(a/c>HIGH/b)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%lld %lld",&l,&r);
            res+=(r-l+1ll);
        }
        printf("%lld",res);
        return 0;
    }
    d=(a/c)*b;
    for(int i=0;i<n;i++)
    {
        scanf("%lld %lld",&l,&r);
        if(r-l+1>=d)
        {
            printf("%lld",d);
            return 0;
        }
        if(l/d==r/d)
        {
            t[cou]={l%d,r%d};
            cou++;
        }
        else
        {
            t[cou]={l%d,d-1ll};
            cou++;
            t[cou]={0ll,r%d};
            cou++;
        }
    }
    sort(t,t+cou);
    for(int i=0;i<cou;i++)
    {
        if(!v.empty() && v[v.size()-1].second>=t[i].first)
        {
            v[v.size()-1].second=max(v[v.size()-1].second,t[i].second);
        }
        else
        {
            v.push_back(t[i]);
        }
    }
    for(int i=0;i<v.size();i++)
    {
        res+=(v[i].second-v[i].first+1ll);
    }
    printf("%lld",res);
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int i=0;i<v.size();i++)
      |                 ~^~~~~~~~~
strange_device.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     scanf("%d %lld %lld",&n,&a,&b);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:28:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |             scanf("%lld %lld",&l,&r);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~
strange_device.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         scanf("%lld %lld",&l,&r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

• 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