oj.uz

Submission #153893

# Submission time Handle Problem Language Result Execution time Memory
153893 2019-09-17T11:05:37 Z DystoriaX Strange Device (APIO19_strange_device) C++14
65 / 100
 646 ms 19528 KB 
#include <bits/stdc++.h>

using namespace std;

int n;
long long a, b, mx;
vector<pair<long long, long long> > seg;

long long gcd(long long a, long long b){
    if(b == 0) return a;
    return gcd(b, a % b);
}

int main(){
    scanf("%d%lld%lld", &n, &a, &b);

    mx = a / gcd(a, b + 1);

    if(log10l(mx) + log10l(b) > 18.1){
        mx = 1e18;
    } else mx *= b;

    for(int i = 0; i < n; i++){
        long long l, r;
        scanf("%lld%lld", &l, &r);

        l %= mx, r %= mx;

        if(r - l + 1 >= mx){
            seg.emplace_back(0, mx - 1);
        } else if (l <= r){
            seg.emplace_back(l, r);
        } else {
            seg.emplace_back(l, mx - 1);
            seg.emplace_back(0, r);
        }
    }

    sort(seg.begin(), seg.end());

    long long ans = 0, last = 0;

    for(auto k : seg){
        ans += max(0LL, k.second - max(last, k.first) + 1);
        last = max(last, k.second + 1);
    }

    printf("%lld\n", ans);
    
    return 0;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:15: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:25: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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 8 ms 888 KB Output is correct
3 Correct 8 ms 1016 KB Output is correct
4 Correct 2 ms 252 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 8 ms 1016 KB Output is correct
17 Correct 65 ms 4072 KB Output is correct
18 Correct 2 ms 248 KB Output is correct

Subtask #2
0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 449 ms 19020 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 571 ms 17848 KB Output is correct
3 Correct 553 ms 17520 KB Output is correct
4 Correct 533 ms 17956 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 571 ms 17848 KB Output is correct
3 Correct 553 ms 17520 KB Output is correct
4 Correct 533 ms 17956 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 552 ms 18408 KB Output is correct
7 Correct 571 ms 18228 KB Output is correct
8 Correct 573 ms 18144 KB Output is correct
9 Correct 599 ms 18128 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 571 ms 17848 KB Output is correct
3 Correct 553 ms 17520 KB Output is correct
4 Correct 533 ms 17956 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 59 ms 3920 KB Output is correct
7 Correct 64 ms 4100 KB Output is correct
8 Correct 55 ms 3788 KB Output is correct
9 Correct 61 ms 3524 KB Output is correct
10 Correct 117 ms 3560 KB Output is correct
11 Correct 60 ms 3560 KB Output is correct
12 Correct 57 ms 3536 KB Output is correct
13 Correct 59 ms 3536 KB Output is correct
14 Correct 57 ms 3492 KB Output is correct
15 Correct 65 ms 3564 KB Output is correct
16 Correct 62 ms 3564 KB Output is correct
17 Correct 57 ms 3616 KB Output is correct
18 Correct 562 ms 18516 KB Output is correct
19 Correct 553 ms 18916 KB Output is correct
20 Correct 599 ms 19116 KB Output is correct
21 Correct 62 ms 4712 KB Output is correct
22 Correct 53 ms 4584 KB Output is correct
23 Correct 239 ms 13056 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 64 ms 4980 KB Output is correct
3 Correct 63 ms 4856 KB Output is correct
4 Correct 646 ms 18984 KB Output is correct
5 Correct 61 ms 4472 KB Output is correct
6 Correct 61 ms 4452 KB Output is correct
7 Correct 59 ms 5196 KB Output is correct
8 Correct 64 ms 4892 KB Output is correct
9 Correct 60 ms 4580 KB Output is correct
10 Correct 61 ms 4400 KB Output is correct
11 Correct 64 ms 4416 KB Output is correct
12 Correct 53 ms 4460 KB Output is correct
13 Correct 62 ms 4588 KB Output is correct
14 Correct 606 ms 19480 KB Output is correct
15 Correct 65 ms 5476 KB Output is correct
16 Correct 561 ms 19528 KB Output is correct
17 Correct 544 ms 19408 KB Output is correct
18 Correct 2 ms 256 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 8 ms 888 KB Output is correct
3 Correct 8 ms 1016 KB Output is correct
4 Correct 2 ms 252 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 8 ms 1016 KB Output is correct
17 Correct 65 ms 4072 KB Output is correct
18 Correct 2 ms 248 KB Output is correct
19 Correct 2 ms 256 KB Output is correct
20 Incorrect 2 ms 252 KB Output isn't correct
21 Halted 0 ms 0 KB -