oj.uz

Submission #153887

# Submission time Handle Problem Language Result Execution time Memory
153887 2019-09-17T10:51:35 Z DystoriaX Strange Device (APIO19_strange_device) C++14
65 / 100
 682 ms 18900 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(log10(mx) + log10(b) > 18){
        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 256 KB Output is correct
2 Correct 8 ms 808 KB Output is correct
3 Correct 8 ms 888 KB Output is correct
4 Correct 2 ms 296 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 376 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 256 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 7 ms 760 KB Output is correct
17 Correct 61 ms 2800 KB Output is correct
18 Correct 2 ms 256 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 256 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 376 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 537 ms 17264 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 525 ms 16948 KB Output is correct
3 Correct 531 ms 16848 KB Output is correct
4 Correct 532 ms 18352 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 525 ms 16948 KB Output is correct
3 Correct 531 ms 16848 KB Output is correct
4 Correct 532 ms 18352 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 530 ms 18900 KB Output is correct
7 Correct 520 ms 18772 KB Output is correct
8 Correct 533 ms 18544 KB Output is correct
9 Correct 601 ms 18644 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 525 ms 16948 KB Output is correct
3 Correct 531 ms 16848 KB Output is correct
4 Correct 532 ms 18352 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 55 ms 4460 KB Output is correct
7 Correct 58 ms 4512 KB Output is correct
8 Correct 54 ms 4172 KB Output is correct
9 Correct 56 ms 4200 KB Output is correct
10 Correct 54 ms 3988 KB Output is correct
11 Correct 57 ms 4024 KB Output is correct
12 Correct 55 ms 4208 KB Output is correct
13 Correct 60 ms 4088 KB Output is correct
14 Correct 54 ms 4072 KB Output is correct
15 Correct 61 ms 4072 KB Output is correct
16 Correct 60 ms 4204 KB Output is correct
17 Correct 57 ms 4360 KB Output is correct
18 Correct 536 ms 18640 KB Output is correct
19 Correct 521 ms 18568 KB Output is correct
20 Correct 602 ms 18384 KB Output is correct
21 Correct 60 ms 4236 KB Output is correct
22 Correct 54 ms 4272 KB Output is correct
23 Correct 207 ms 11040 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 59 ms 4220 KB Output is correct
3 Correct 60 ms 4512 KB Output is correct
4 Correct 619 ms 18640 KB Output is correct
5 Correct 59 ms 4208 KB Output is correct
6 Correct 61 ms 3948 KB Output is correct
7 Correct 60 ms 4200 KB Output is correct
8 Correct 64 ms 4072 KB Output is correct
9 Correct 60 ms 4056 KB Output is correct
10 Correct 59 ms 4048 KB Output is correct
11 Correct 62 ms 4032 KB Output is correct
12 Correct 54 ms 4004 KB Output is correct
13 Correct 62 ms 4072 KB Output is correct
14 Correct 682 ms 18256 KB Output is correct
15 Correct 58 ms 3948 KB Output is correct
16 Correct 543 ms 18132 KB Output is correct
17 Correct 527 ms 17872 KB Output is correct
18 Correct 2 ms 248 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 8 ms 808 KB Output is correct
3 Correct 8 ms 888 KB Output is correct
4 Correct 2 ms 296 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 376 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 256 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 7 ms 760 KB Output is correct
17 Correct 61 ms 2800 KB Output is correct
18 Correct 2 ms 256 KB Output is correct
19 Correct 2 ms 256 KB Output is correct
20 Incorrect 2 ms 256 KB Output isn't correct
21 Halted 0 ms 0 KB -