oj.uz

Submission #153890

# Submission time Handle Problem Language Result Execution time Memory
153890 2019-09-17T10:58:30 Z DystoriaX Strange Device (APIO19_strange_device) C++14
65 / 100
 626 ms 19280 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){
        mx = 1000000000000000000LL;
    } 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 9 ms 1016 KB Output is correct
3 Correct 9 ms 1016 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 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 376 KB Output is correct
9 Correct 1 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 256 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 4588 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 4 ms 376 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 4 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 422 ms 19000 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 574 ms 19048 KB Output is correct
3 Correct 554 ms 19096 KB Output is correct
4 Correct 535 ms 19280 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 574 ms 19048 KB Output is correct
3 Correct 554 ms 19096 KB Output is correct
4 Correct 535 ms 19280 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 553 ms 18868 KB Output is correct
7 Correct 571 ms 18980 KB Output is correct
8 Correct 551 ms 19240 KB Output is correct
9 Correct 595 ms 19192 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 574 ms 19048 KB Output is correct
3 Correct 554 ms 19096 KB Output is correct
4 Correct 535 ms 19280 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 58 ms 4988 KB Output is correct
7 Correct 60 ms 5220 KB Output is correct
8 Correct 55 ms 5480 KB Output is correct
9 Correct 59 ms 5424 KB Output is correct
10 Correct 58 ms 5476 KB Output is correct
11 Correct 60 ms 5492 KB Output is correct
12 Correct 55 ms 5480 KB Output is correct
13 Correct 60 ms 5476 KB Output is correct
14 Correct 60 ms 5476 KB Output is correct
15 Correct 63 ms 5400 KB Output is correct
16 Correct 63 ms 5548 KB Output is correct
17 Correct 58 ms 5348 KB Output is correct
18 Correct 566 ms 18900 KB Output is correct
19 Correct 626 ms 18648 KB Output is correct
20 Correct 617 ms 18536 KB Output is correct
21 Correct 62 ms 4332 KB Output is correct
22 Correct 58 ms 4164 KB Output is correct
23 Correct 210 ms 11920 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 424 KB Output is correct
2 Correct 62 ms 4076 KB Output is correct
3 Correct 78 ms 4176 KB Output is correct
4 Correct 623 ms 18420 KB Output is correct
5 Correct 61 ms 4372 KB Output is correct
6 Correct 61 ms 4332 KB Output is correct
7 Correct 60 ms 3944 KB Output is correct
8 Correct 63 ms 4180 KB Output is correct
9 Correct 65 ms 4456 KB Output is correct
10 Correct 61 ms 4328 KB Output is correct
11 Correct 63 ms 4200 KB Output is correct
12 Correct 56 ms 4236 KB Output is correct
13 Correct 63 ms 4176 KB Output is correct
14 Correct 611 ms 18032 KB Output is correct
15 Correct 62 ms 3328 KB Output is correct
16 Correct 553 ms 17364 KB Output is correct
17 Correct 553 ms 17316 KB Output is correct
18 Correct 2 ms 252 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 9 ms 1016 KB Output is correct
3 Correct 9 ms 1016 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 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 376 KB Output is correct
9 Correct 1 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 256 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 4588 KB Output is correct
18 Correct 2 ms 256 KB Output is correct
19 Correct 2 ms 256 KB Output is correct
20 Incorrect 4 ms 376 KB Output isn't correct
21 Halted 0 ms 0 KB -