oj.uz

Submission #125395

# Submission time Handle Problem Language Result Execution time Memory
125395 2019-07-05T07:50:35 Z mlyean00 Strange Device (APIO19_strange_device) C++17
15 / 100
 759 ms 17468 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) > 62)
        mod = MAX;
    else
        mod = min(A * B, MAX);

    // The intervals to union
    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 + 1 < 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 376 KB Output is correct
2 Incorrect 8 ms 888 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 348 KB Output is correct
2 Correct 2 ms 292 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 380 KB Output is correct
2 Incorrect 3 ms 376 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 759 ms 16988 KB Output is correct
3 Correct 605 ms 17380 KB Output is correct
4 Correct 589 ms 17368 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 759 ms 16988 KB Output is correct
3 Correct 605 ms 17380 KB Output is correct
4 Correct 589 ms 17368 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 587 ms 17392 KB Output is correct
7 Correct 591 ms 17468 KB Output is correct
8 Correct 597 ms 17096 KB Output is correct
9 Correct 647 ms 17280 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 759 ms 16988 KB Output is correct
3 Correct 605 ms 17380 KB Output is correct
4 Correct 589 ms 17368 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 59 ms 2756 KB Output is correct
7 Correct 63 ms 2824 KB Output is correct
8 Correct 60 ms 2800 KB Output is correct
9 Correct 63 ms 2800 KB Output is correct
10 Correct 59 ms 2800 KB Output is correct
11 Correct 62 ms 2796 KB Output is correct
12 Correct 59 ms 2804 KB Output is correct
13 Correct 67 ms 2796 KB Output is correct
14 Correct 61 ms 2812 KB Output is correct
15 Incorrect 68 ms 2928 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 65 ms 2896 KB Output is correct
3 Correct 66 ms 2748 KB Output is correct
4 Correct 701 ms 17236 KB Output is correct
5 Correct 66 ms 3044 KB Output is correct
6 Correct 66 ms 3060 KB Output is correct
7 Correct 66 ms 2992 KB Output is correct
8 Correct 65 ms 3036 KB Output is correct
9 Correct 69 ms 3028 KB Output is correct
10 Correct 64 ms 3056 KB Output is correct
11 Correct 66 ms 2988 KB Output is correct
12 Correct 58 ms 3092 KB Output is correct
13 Correct 65 ms 3004 KB Output is correct
14 Incorrect 653 ms 17432 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 376 KB Output is correct
2 Incorrect 8 ms 888 KB Output isn't correct
3 Halted 0 ms 0 KB -