Submission #145581

#	Time	Username	Problem	Language	Result	Execution time	Memory
145581		mhy908	Strange Device (APIO19_strange_device)	C++14	100 / 100	739 ms	18896 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
int n;
LL a, b;
bool iscalc=true;
LL gcd(LL x, LL y)
{
    if(!y)return x;
    return gcd(y, x%y);
}
vector<pll> vc;
int main()
{
    scanf("%d %lld %lld", &n, &a, &b);
    LL temp=a/gcd(a, b+1);
    LL pv=0;
    LL ans=0;
    if(log10(temp)+log10(b)>=18.1)iscalc=false;
    else temp*=b;
    for(int i=1; i<=n; i++){
        LL x, y;
        scanf("%lld %lld", &x, &y);
        if(!iscalc){
            vc.push_back({x, y});
            continue;
        }
        LL xx=x%temp;
        LL yy=y%temp;
        if(x==y)vc.push_back({xx, xx});
        else{
            if(x/temp==y/temp)vc.push_back({xx, yy});
            else if(x/temp+1==y/temp&&xx>=yy)vc.push_back({xx, temp-1}), vc.push_back({0, yy});
            else vc.push_back({0, temp-1});
        }
    }
    sort(vc.begin(), vc.end());
    for(int i=0; i<vc.size(); i++){
        LL e=vc[i].first, r=vc[i].second;
        ans+=(max(pv, vc[i].first)>vc[i].second?0:vc[i].second-max(pv, vc[i].first)+1);
        pv=max(vc[i].second+1, pv);
    }
    printf("%lld", ans);
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:40:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<vc.size(); i++){
                  ~^~~~~~~~~~
strange_device.cpp:41:12: warning: unused variable 'e' [-Wunused-variable]
         LL e=vc[i].first, r=vc[i].second;
            ^
strange_device.cpp:41:27: warning: unused variable 'r' [-Wunused-variable]
         LL e=vc[i].first, r=vc[i].second;
                           ^
strange_device.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %lld %lld", &n, &a, &b);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:25:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~

• 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