oj.uz

Submission #258391

# Submission time Handle Problem Language Result Execution time Memory
258391 2020-08-05T21:14:40 Z DS007 Strange Device (APIO19_strange_device) C++14
35 / 100
 792 ms 35272 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, a, b;

bool overflow(int x, int y) {
    return (x * y) / x != y;
}

int sum() {
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        ans += r - l + 1;
    }
    return ans;
}

int solveTestCase() {
    cin >> n >> a >> b;

    int temp = a / __gcd(a, b + 1);
    if (overflow(temp, b))
        return cout << sum(), 0;

    temp *= b;
    //cerr << temp << "\n";
    vector<pair<int, int>> v;

    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;

        if (r - l >= temp)
            return cout << temp, 0;

        if (l % temp <= r % temp)
            v.emplace_back(l % temp, 1), v.emplace_back(r % temp + 1, 2);
        else
            v.emplace_back(l % temp, 1), v.emplace_back(temp, 2), v.emplace_back(0, 1), v.emplace_back(r % temp + 1, 2);
    }

    sort(v.begin(), v.end());

    int ans = 0, d = 0, last = 0;
    for (auto i : v) {
        if (d == 0)
            last = i.first;

        if (i.second == 1)
            d++;
        else
            d--;

        assert(d >= 0);
        if (d == 0)
            ans += i.first - last;
    }

    cout << ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
    //cin >> t;
    while (t--)
        solveTestCase();
}

Compilation message

strange_device.cpp: In function 'long long int solveTestCase()':
strange_device.cpp:63:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 6 ms 1448 KB Output is correct
3 Correct 6 ms 1408 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 8 ms 1408 KB Output is correct
17 Correct 81 ms 7276 KB Output is correct
18 Incorrect 1 ms 384 KB Output isn't correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Incorrect 1 ms 384 KB Output isn't correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 404 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 416 ms 34272 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 636 ms 35104 KB Output is correct
3 Correct 658 ms 35152 KB Output is correct
4 Correct 604 ms 35136 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 636 ms 35104 KB Output is correct
3 Correct 658 ms 35152 KB Output is correct
4 Correct 604 ms 35136 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 623 ms 35136 KB Output is correct
7 Correct 652 ms 35136 KB Output is correct
8 Correct 637 ms 35120 KB Output is correct
9 Correct 780 ms 35136 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 636 ms 35104 KB Output is correct
3 Correct 658 ms 35152 KB Output is correct
4 Correct 604 ms 35136 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 64 ms 7272 KB Output is correct
7 Correct 67 ms 7396 KB Output is correct
8 Correct 58 ms 7320 KB Output is correct
9 Correct 61 ms 7272 KB Output is correct
10 Correct 57 ms 7276 KB Output is correct
11 Correct 68 ms 7276 KB Output is correct
12 Correct 60 ms 7396 KB Output is correct
13 Correct 78 ms 7396 KB Output is correct
14 Correct 63 ms 7276 KB Output is correct
15 Correct 76 ms 7384 KB Output is correct
16 Correct 73 ms 7276 KB Output is correct
17 Correct 60 ms 7436 KB Output is correct
18 Correct 631 ms 35136 KB Output is correct
19 Correct 632 ms 35120 KB Output is correct
20 Correct 792 ms 35136 KB Output is correct
21 Correct 74 ms 7372 KB Output is correct
22 Correct 60 ms 7284 KB Output is correct
23 Correct 192 ms 26800 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 72 ms 7272 KB Output is correct
3 Correct 71 ms 7276 KB Output is correct
4 Correct 771 ms 35272 KB Output is correct
5 Correct 68 ms 7284 KB Output is correct
6 Correct 70 ms 7276 KB Output is correct
7 Correct 69 ms 7276 KB Output is correct
8 Correct 74 ms 7392 KB Output is correct
9 Correct 64 ms 7272 KB Output is correct
10 Correct 75 ms 7276 KB Output is correct
11 Correct 70 ms 7284 KB Output is correct
12 Correct 61 ms 7424 KB Output is correct
13 Correct 69 ms 7272 KB Output is correct
14 Correct 735 ms 35220 KB Output is correct
15 Correct 75 ms 7396 KB Output is correct
16 Correct 617 ms 35132 KB Output is correct
17 Correct 643 ms 35208 KB Output is correct
18 Incorrect 1 ms 384 KB Output isn't correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 6 ms 1448 KB Output is correct
3 Correct 6 ms 1408 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 8 ms 1408 KB Output is correct
17 Correct 81 ms 7276 KB Output is correct
18 Incorrect 1 ms 384 KB Output isn't correct