oj.uz

Submission #407022

# Submission time Handle Problem Language Result Execution time Memory
407022 2021-05-18T11:10:42 Z tengiz05 Strange Device (APIO19_strange_device) C++17
35 / 100
 1584 ms 60816 KB 
#include <bits/stdc++.h>
using i64 = long long;
constexpr i64 inf = 2e18 + 100;
int main(){
    i64 n, A, B;
    std::cin >> n >> A >> B;
    i64 gcd = std::__gcd(A, B + 1);
    i64 cycle = A / gcd;
    if (inf / gcd < B) {
        cycle = inf;
    } else {
        cycle *= B;
    }
    std::vector<std::pair<i64, i64>> v;
    for (int i = 0; i < n; i++) {
        i64 l, r;
        std::cin >> l >> r;
        l %= cycle;
        r %= cycle;
        if (r - l + 1 >= cycle) {
            std::cout << cycle << "\n";
            return 0;
        }
        if (l <= r) {
            v.emplace_back(l, r);
        } else {
            v.emplace_back(0, r);
            v.emplace_back(l, cycle - 1);
        }
    }
    sort(v.begin(), v.end());
    std::vector<std::pair<i64, i64>> nw;
    nw.push_back(v[0]);
    for (int i = 1; i < int(v.size()); i++) {
        if (nw[nw.size() - 1].second >= v[i].first) {
            nw[nw.size() - 1].first = std::min(nw[nw.size() - 1].first, v[i].first);
            nw[nw.size() - 1].second = std::max(nw[nw.size() - 1].second, v[i].second);
        } else {
            nw.emplace_back(v[i]);
        }
    }
    i64 ans = 0;
    for (auto [l, r] : nw) {
        ans += r - l + 1;
    }
    std::cout << ans << '\n';
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 16 ms 1100 KB Output is correct
3 Correct 16 ms 1192 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 292 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 288 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 288 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 292 KB Output is correct
16 Correct 16 ms 1152 KB Output is correct
17 Correct 155 ms 8612 KB Output is correct
18 Incorrect 1 ms 204 KB Output isn't correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 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 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 1132 ms 21700 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1553 ms 60480 KB Output is correct
3 Correct 1496 ms 60816 KB Output is correct
4 Correct 1576 ms 60604 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1553 ms 60480 KB Output is correct
3 Correct 1496 ms 60816 KB Output is correct
4 Correct 1576 ms 60604 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1563 ms 60676 KB Output is correct
7 Correct 1502 ms 42516 KB Output is correct
8 Correct 1508 ms 42320 KB Output is correct
9 Correct 1528 ms 42268 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1553 ms 60480 KB Output is correct
3 Correct 1496 ms 60816 KB Output is correct
4 Correct 1576 ms 60604 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 151 ms 8644 KB Output is correct
7 Correct 177 ms 8536 KB Output is correct
8 Correct 148 ms 8564 KB Output is correct
9 Correct 155 ms 8632 KB Output is correct
10 Correct 151 ms 8600 KB Output is correct
11 Correct 154 ms 8544 KB Output is correct
12 Correct 148 ms 8544 KB Output is correct
13 Correct 175 ms 8672 KB Output is correct
14 Correct 152 ms 8572 KB Output is correct
15 Correct 153 ms 8748 KB Output is correct
16 Correct 159 ms 8728 KB Output is correct
17 Correct 166 ms 8556 KB Output is correct
18 Correct 1506 ms 60656 KB Output is correct
19 Correct 1500 ms 60476 KB Output is correct
20 Correct 1560 ms 60556 KB Output is correct
21 Correct 153 ms 8600 KB Output is correct
22 Correct 147 ms 8604 KB Output is correct
23 Correct 494 ms 18528 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 155 ms 8676 KB Output is correct
3 Correct 160 ms 8644 KB Output is correct
4 Correct 1584 ms 60416 KB Output is correct
5 Correct 154 ms 8624 KB Output is correct
6 Correct 160 ms 8604 KB Output is correct
7 Correct 181 ms 8572 KB Output is correct
8 Correct 156 ms 8728 KB Output is correct
9 Correct 151 ms 8532 KB Output is correct
10 Correct 152 ms 8612 KB Output is correct
11 Correct 154 ms 8516 KB Output is correct
12 Correct 155 ms 8724 KB Output is correct
13 Correct 158 ms 8624 KB Output is correct
14 Correct 1540 ms 60540 KB Output is correct
15 Correct 175 ms 8640 KB Output is correct
16 Correct 1477 ms 60484 KB Output is correct
17 Correct 1490 ms 60584 KB Output is correct
18 Incorrect 1 ms 204 KB Output isn't correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 16 ms 1100 KB Output is correct
3 Correct 16 ms 1192 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 292 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 288 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 288 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 292 KB Output is correct
16 Correct 16 ms 1152 KB Output is correct
17 Correct 155 ms 8612 KB Output is correct
18 Incorrect 1 ms 204 KB Output isn't correct