Submission #531647

#	Time	Username	Problem	Language	Result	Execution time	Memory
531647		79brue	Strange Device (APIO19_strange_device)	C++14	5 / 100	507 ms	69564 KiB

strange_device

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
ll a, b;
ll l[1000002], r[1000002];

int main(){
    scanf("%d %lld %lld", &n, &a, &b);
    for(int i=1; i<=n; i++) scanf("%lld %lld", &l[i], &r[i]);

    if(1000000000000000000LL / a + 1 <= b){
        ll ans = 0;
        for(int i=1; i<=n; i++) ans += r[i] - l[i] + 1;
        printf("%lld", ans);
        return 0;
    }

    a = a*b;
    for(int i=1; i<=n; i++){
        if(r[i] - l[i] >= a-1){
            printf("%lld", a);
            return 0;
        }
    }

    vector<pair<ll, ll> > vec;
    for(int i=1; i<=n; i++){
        if(l[i]%a <= r[i]%a) vec.push_back(make_pair(l[i]%a, r[i]%a));
        else{
            vec.push_back(make_pair(0, r[i]%a));
            vec.push_back(make_pair(l[i]%a, a-1));
        }
    }
    sort(vec.begin(), vec.end());

    ll ans = 0;
    ll rMax = vec[0].second;
    ll lPnt = vec[0].first;
    for(int i=0; i<(int)vec.size(); i++){
        rMax = max(rMax, vec[i].second);
        if(i<(int)vec.size()-1 && vec[i].second < vec[i+1].first){
            ans += rMax - lPnt + 1;
            lPnt = vec[i+1].first;
        }
        else if(i==(int)vec.size()-1){
            ans += rMax - lPnt + 1;
        }
        else{
            rMax = max(rMax, vec[i].second);
        }
    }
    printf("%lld", ans);
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     scanf("%d %lld %lld", &n, &a, &b);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:13:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     for(int i=1; i<=n; i++) scanf("%lld %lld", &l[i], &r[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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