Submission #250229

#	Time	Username	Problem	Language	Result	Execution time	Memory
250229		errorgorn	Strange Device (APIO19_strange_device)	C++14	100 / 100	637 ms	61500 KiB

strange_device

#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
typedef pair<long long,long long> ii;

vector<ii> compress_ranges(vector<ii> ranges){
    sort(ranges.begin(),ranges.end());
    vector<ii> r;
    r.push_back(ranges[0]);
    for (int x=1;x<ranges.size();x++){
        if (r.back().second>=ranges[x].first){
           r.back().second=max(r.back().second,ranges[x].second);
        }
        else{
            r.push_back(ranges[x]);
        }
    }
    return r;
}


int n;
long long a,b;
vector<ii> v;
int main(){
    scanf("%d%lld%lld",&n,&a,&b);
    
    long long mod=(a/__gcd(a,b+1)>2000000000000000000/b)?2000000000000000000:a/__gcd(a,b+1)*b;
    
    long long l,r;
    for (int x=0;x<n;x++){
        scanf("%lld%lld",&l,&r);
        if (r-l+1>=mod) v.push_back(ii(0,mod-1));
        else{
            l%=mod,r%=mod;
            if (l<=r) v.push_back(ii(l,r));
            else v.push_back(ii(l,mod-1)),v.push_back(ii(0,r));
        }
    }
    
    v=compress_ranges(v);
    
    long long ans=0;
    for (int x=0;x<v.size();x++){
        ans+=v[x].second-v[x].first+1;
    }
    
    printf("%lld\n",ans);
}

Compilation message (stderr)

strange_device.cpp: In function 'std::vector<std::pair<long long int, long long int> > compress_ranges(std::vector<std::pair<long long int, long long int> >)':
strange_device.cpp:12:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int x=1;x<ranges.size();x++){
                  ~^~~~~~~~~~~~~~
strange_device.cpp: In function 'int main()':
strange_device.cpp:46:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int x=0;x<v.size();x++){
                  ~^~~~~~~~~
strange_device.cpp:28: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:34:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         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