Submission #1003743

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003743		underwaterkillerwhale	Strange Device (APIO19_strange_device)	C++17	65 / 100	345 ms	69820 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/__gcd(a, b+1)) * b;
    
 
    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 && rMax < 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: 10 / 10
• Subtask 2: 0 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20
• Subtask 8: 0 / 30