oj.uz

Submission #531647

# Submission time Handle Problem Language Result Execution time Memory
531647 2022-03-01T07:55:46 Z 79brue Strange Device (APIO19_strange_device) C++14
5 / 100
 507 ms 69564 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 5 ms 1228 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 1 ms 312 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Incorrect 507 ms 69564 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Incorrect 507 ms 69564 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Incorrect 507 ms 69564 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Incorrect 49 ms 7752 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 5 ms 1228 KB Output isn't correct
3 Halted 0 ms 0 KB -