oj.uz

Submission #125390

# Submission time Handle Problem Language Result Execution time Memory
125390 2019-07-05T07:32:55 Z mlyean00 Strange Device (APIO19_strange_device) C++17
15 / 100
 725 ms 41176 KB 
#ifdef DEBUG
#define trace(x) cerr << "DEBUG: " << (#x) << " = " << (x) << endl
#else
#pragma GCC optimize("Ofast")
#define trace(x)
#endif

#include <bits/stdc++.h>

#define endl '\n'

using namespace std;
using ll = long long;

const ll MAX = 1'000'000'000'000'000'001LL;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    ll A, B;
    cin >> n >> A >> B;

    ll g = gcd(A, B + 1);
    A /= g;

    ll mod;
    // Check overflow
    if (__lg(A) + __lg(B) > 60)
        mod = MAX;
    else
        mod = min(A * B, MAX);

    // The intervals to intersect
    vector<pair<ll, ll>> v;

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

        // Shift left endpoint such that 0 <= l < mod
        ll k = (l / mod) * mod;
        l -= k;
        r -= k;

        if (r - l + 1 >= mod) {
            v.emplace_back(0, mod - 1);
        } else if (r < mod) {
            v.emplace_back(l, r);
        } else {
            v.emplace_back(l, mod - 1);
            v.emplace_back(0, r - mod);
        }
    }

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

    // Merge intervals
    vector<pair<ll, ll>> v_merged;
    v_merged.push_back(v.front());

    for (int i = 1; i < v.size(); ++i) {
        auto& last = v_merged.back();
        if (last.second < v[i].first) {
            v_merged.push_back(v[i]);
        } else {
            last.second = v[i].second;
        }
    }

    ll ans = 0;
    for (auto [l, r] : v_merged) {
        ans += r - l + 1;
    }

    cout << ans << endl;

    return 0;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:63:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < v.size(); ++i) {
                     ~~^~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Incorrect 8 ms 1328 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
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 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 3 ms 472 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 624 ms 41176 KB Output is correct
3 Correct 646 ms 41024 KB Output is correct
4 Correct 705 ms 41056 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 624 ms 41176 KB Output is correct
3 Correct 646 ms 41024 KB Output is correct
4 Correct 705 ms 41056 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 642 ms 41052 KB Output is correct
7 Correct 622 ms 40900 KB Output is correct
8 Correct 616 ms 41044 KB Output is correct
9 Correct 680 ms 40876 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 624 ms 41176 KB Output is correct
3 Correct 646 ms 41024 KB Output is correct
4 Correct 705 ms 41056 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 64 ms 6016 KB Output is correct
7 Correct 67 ms 5520 KB Output is correct
8 Correct 63 ms 5548 KB Output is correct
9 Correct 65 ms 5544 KB Output is correct
10 Correct 63 ms 5520 KB Output is correct
11 Correct 65 ms 5544 KB Output is correct
12 Correct 63 ms 5500 KB Output is correct
13 Correct 70 ms 5484 KB Output is correct
14 Correct 62 ms 5484 KB Output is correct
15 Incorrect 70 ms 5480 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 68 ms 5832 KB Output is correct
3 Correct 68 ms 5356 KB Output is correct
4 Correct 725 ms 40908 KB Output is correct
5 Correct 69 ms 5296 KB Output is correct
6 Correct 68 ms 5324 KB Output is correct
7 Correct 68 ms 5352 KB Output is correct
8 Correct 70 ms 5332 KB Output is correct
9 Correct 67 ms 5324 KB Output is correct
10 Correct 67 ms 5328 KB Output is correct
11 Correct 67 ms 5352 KB Output is correct
12 Correct 61 ms 5352 KB Output is correct
13 Correct 68 ms 5312 KB Output is correct
14 Incorrect 667 ms 40912 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Incorrect 8 ms 1328 KB Output isn't correct
3 Halted 0 ms 0 KB -