oj.uz

Submission #171601

# Submission time Handle Problem Language Result Execution time Memory
171601 2019-12-29T11:00:19 Z rama_pang Strange Device (APIO19_strange_device) C++14
65 / 100
 791 ms 19948 KB 
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint INF = 1e18 + 100;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int n;
    lint A, B;
    cin >> n >> A >> B;
    lint g = __gcd(A, B + 1);
    lint t = 0;

    if (A / g >= (INF / B) + 1) {
        t = INF;
    } else {
        t = (A / g) * B;
    }

    deque<pair<lint, lint>> interval;
    
    for (int i = 0; i < n; i++) {
        lint l, r;
        cin >> l >> r;
        l %= t;
        r %= t;
        if (l <= r) {
            interval.emplace_back(l, r);
        } else {
            interval.emplace_back(l, t - 1);
            interval.emplace_back(0, r);
        }
    }

    sort(begin(interval), end(interval));
    lint ans = 0;

    for (int i = 0; i < (int)interval.size(); i++) {
        lint l = interval[i].first;
        lint r = interval[i].second;
        int nxt = i;
        while (nxt + 1 < (int)interval.size() && interval[nxt + 1].first <= r) {
            r = max(r, interval[nxt + 1].second);
            nxt++;
        }
        ans += (r - l + 1);
        i = nxt;
    }

    cout << ans << "\n";
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 8 ms 760 KB Output is correct
3 Correct 9 ms 888 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 380 KB Output is correct
15 Correct 2 ms 504 KB Output is correct
16 Correct 8 ms 892 KB Output is correct
17 Correct 76 ms 4088 KB Output is correct
18 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 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 376 KB Output is correct
2 Correct 2 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 450 ms 16912 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 656 ms 19948 KB Output is correct
3 Correct 651 ms 16792 KB Output is correct
4 Correct 654 ms 16968 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 656 ms 19948 KB Output is correct
3 Correct 651 ms 16792 KB Output is correct
4 Correct 654 ms 16968 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 654 ms 16872 KB Output is correct
7 Correct 671 ms 16940 KB Output is correct
8 Correct 667 ms 16936 KB Output is correct
9 Correct 775 ms 19116 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 656 ms 19948 KB Output is correct
3 Correct 651 ms 16792 KB Output is correct
4 Correct 654 ms 16968 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 64 ms 4008 KB Output is correct
7 Correct 70 ms 3960 KB Output is correct
8 Correct 66 ms 4016 KB Output is correct
9 Correct 68 ms 4088 KB Output is correct
10 Correct 63 ms 4088 KB Output is correct
11 Correct 68 ms 4088 KB Output is correct
12 Correct 64 ms 4088 KB Output is correct
13 Correct 74 ms 4060 KB Output is correct
14 Correct 63 ms 4080 KB Output is correct
15 Correct 76 ms 4088 KB Output is correct
16 Correct 74 ms 4088 KB Output is correct
17 Correct 68 ms 4088 KB Output is correct
18 Correct 679 ms 18856 KB Output is correct
19 Correct 655 ms 18604 KB Output is correct
20 Correct 780 ms 18476 KB Output is correct
21 Correct 76 ms 3704 KB Output is correct
22 Correct 64 ms 3704 KB Output is correct
23 Correct 195 ms 7032 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 72 ms 2524 KB Output is correct
3 Correct 74 ms 3420 KB Output is correct
4 Correct 791 ms 16984 KB Output is correct
5 Correct 74 ms 3448 KB Output is correct
6 Correct 75 ms 3448 KB Output is correct
7 Correct 75 ms 3420 KB Output is correct
8 Correct 77 ms 3436 KB Output is correct
9 Correct 72 ms 3320 KB Output is correct
10 Correct 73 ms 3448 KB Output is correct
11 Correct 73 ms 3432 KB Output is correct
12 Correct 62 ms 3320 KB Output is correct
13 Correct 73 ms 3192 KB Output is correct
14 Correct 759 ms 18084 KB Output is correct
15 Correct 71 ms 3064 KB Output is correct
16 Correct 657 ms 17756 KB Output is correct
17 Correct 643 ms 16816 KB Output is correct
18 Correct 2 ms 376 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 8 ms 760 KB Output is correct
3 Correct 9 ms 888 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 380 KB Output is correct
15 Correct 2 ms 504 KB Output is correct
16 Correct 8 ms 892 KB Output is correct
17 Correct 76 ms 4088 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Incorrect 2 ms 376 KB Output isn't correct
21 Halted 0 ms 0 KB -