oj.uz

Submission #171600

# Submission time Handle Problem Language Result Execution time Memory
171600 2019-12-29T10:54:03 Z rama_pang Strange Device (APIO19_strange_device) C++14
65 / 100
 799 ms 52652 KB 
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint INF = 1e18 + 1;

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) {
        t = INF + 1;
    } 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 888 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 376 KB Output is correct
7 Correct 2 ms 376 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 380 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 376 KB Output is correct
16 Correct 8 ms 888 KB Output is correct
17 Correct 76 ms 5752 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 380 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 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 453 ms 41636 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 28080 KB Output is correct
3 Correct 658 ms 33600 KB Output is correct
4 Correct 648 ms 34344 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 28080 KB Output is correct
3 Correct 658 ms 33600 KB Output is correct
4 Correct 648 ms 34344 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 667 ms 44832 KB Output is correct
7 Correct 659 ms 51116 KB Output is correct
8 Correct 660 ms 51264 KB Output is correct
9 Correct 779 ms 46456 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 28080 KB Output is correct
3 Correct 658 ms 33600 KB Output is correct
4 Correct 648 ms 34344 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 62 ms 5712 KB Output is correct
7 Correct 71 ms 5752 KB Output is correct
8 Correct 66 ms 5884 KB Output is correct
9 Correct 69 ms 5628 KB Output is correct
10 Correct 64 ms 5744 KB Output is correct
11 Correct 73 ms 5624 KB Output is correct
12 Correct 65 ms 5752 KB Output is correct
13 Correct 75 ms 5716 KB Output is correct
14 Correct 62 ms 5624 KB Output is correct
15 Correct 76 ms 5704 KB Output is correct
16 Correct 74 ms 5728 KB Output is correct
17 Correct 68 ms 5676 KB Output is correct
18 Correct 786 ms 46664 KB Output is correct
19 Correct 655 ms 46248 KB Output is correct
20 Correct 770 ms 46500 KB Output is correct
21 Correct 76 ms 5768 KB Output is correct
22 Correct 62 ms 5652 KB Output is correct
23 Correct 196 ms 18660 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 76 ms 2680 KB Output is correct
3 Correct 80 ms 5624 KB Output is correct
4 Correct 799 ms 52652 KB Output is correct
5 Correct 73 ms 5624 KB Output is correct
6 Correct 73 ms 5628 KB Output is correct
7 Correct 73 ms 5752 KB Output is correct
8 Correct 75 ms 5644 KB Output is correct
9 Correct 72 ms 5684 KB Output is correct
10 Correct 73 ms 5752 KB Output is correct
11 Correct 82 ms 5688 KB Output is correct
12 Correct 66 ms 5752 KB Output is correct
13 Correct 164 ms 5752 KB Output is correct
14 Correct 757 ms 47128 KB Output is correct
15 Correct 71 ms 5752 KB Output is correct
16 Correct 657 ms 47356 KB Output is correct
17 Correct 667 ms 52172 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 888 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 376 KB Output is correct
7 Correct 2 ms 376 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 380 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 376 KB Output is correct
16 Correct 8 ms 888 KB Output is correct
17 Correct 76 ms 5752 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 380 KB Output isn't correct
21 Halted 0 ms 0 KB -