Submission #197510

#	Time	Username	Problem	Language	Result	Execution time	Memory
197510		handlename	Strange Device (APIO19_strange_device)	C++17	100 / 100	751 ms	53440 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;
long long n,a,b,l,r,m,ans;
vector<pair<long long,long long> > arr;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>a>>b;
    a=a/(__gcd(a,b+1));
    if (b>1e18/a){
        while (n--){
            cin>>l>>r;
            ans+=r-l+1;
        }
        cout<<ans;
        return 0;
    }
    m=a*b;
    while (n--){
        cin>>l>>r;
        if (r-m>=l){
            cout<<m;
            return 0;
        }
        if (l/m==r/m) arr.push_back(make_pair(l%m,r%m));
        else {
            arr.push_back(make_pair(0,r%m));
            arr.push_back(make_pair(l%m,m-1));
        }
    }
    sort(arr.begin(),arr.end());
    long long s=arr[0].first,e=arr[0].second;
    for (int i=1;i<arr.size();i++){
        if (arr[i].first>e){
            ans+=e-s+1;
            s=arr[i].first;
            e=arr[i].second;
        }
        else {
            e=max(e,arr[i].second);
        }
    }
    ans+=e-s+1;
    cout<<ans;
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:33:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=1;i<arr.size();i++){
                  ~^~~~~~~~~~~

• 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