oj.uz

Submission #848249

# Submission time Handle Problem Language Result Execution time Memory
848249 2023-09-11T20:28:03 Z popovicirobert Strange Device (APIO19_strange_device) C++14
15 / 100
 894 ms 78828 KB 
#include <bits/stdc++.h>

#define lsb(x) (x & (-x))

using ull = unsigned long long;
using ll = long long;

using namespace std;

constexpr ll INF = 2e18;

int main() {
#ifdef HOME
    ifstream cin("input.in");
    ofstream cout("output.out");
#endif
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int n;
    ll a, b;
    cin >> n >> a >> b;

    vector<pair<ll, ll>> segs(n);
    ll sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> segs[i].first >> segs[i].second;
        sum += segs[i].second - segs[i].first + 1;
    }

    if (INF / a < b / __gcd(a, b + 1)) {
        cout << sum;
        return 0;
    }

    multiset<pair<ll, ll>> mst;

    ll period = (a / __gcd(a, b + 1)) * b;

    for (int i = 0; i < n; i++) {
        ll l, r;
        tie(l, r) = segs[i];

        if (r - l + 1 >= period) {
            cout << period << "\n";
            return 0;
        }

        auto Add = [&](ll l, ll r) {
            ll new_l = l, new_r = r;
            vector<pair<ll, ll>> temp;

            auto itr = mst.insert({l, r});

            auto prv = itr;
            while (prv != mst.begin() && prv->second >= l) {
                new_l = min(new_l, prv->first);
                temp.push_back(*prv);
                prv = prev(prv);
            }
            if (prv->second >= l) {
                new_l = min(new_l, prv->first);
                temp.push_back(*prv);
            }

            auto nxt = itr;
            while (nxt != mst.end() && nxt->first <= r) {
                new_r = max(new_r, nxt->second);
                temp.push_back(*nxt);
                nxt = next(nxt);
            }

            for (auto s : temp) {
                mst.erase(s);
            }

            mst.insert({new_l, new_r});
        };

        l %= period;
        r %= period;

        if (l > r) {
            Add(l, period - 1);
            Add(0, r);
        } else {
            Add(l, r);
        }
    }

    ll answer = 0;
    for (auto itr : mst) {
        answer += itr.second - itr.first + 1;
    }

    cout << answer;

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 6 ms 1112 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 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 1 ms 344 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 0 ms 344 KB Output is correct
2 Correct 725 ms 78580 KB Output is correct
3 Correct 710 ms 78572 KB Output is correct
4 Correct 793 ms 78616 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 725 ms 78580 KB Output is correct
3 Correct 710 ms 78572 KB Output is correct
4 Correct 793 ms 78616 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 687 ms 78672 KB Output is correct
7 Correct 723 ms 78464 KB Output is correct
8 Correct 702 ms 78744 KB Output is correct
9 Correct 855 ms 78764 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 725 ms 78580 KB Output is correct
3 Correct 710 ms 78572 KB Output is correct
4 Correct 793 ms 78616 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 55 ms 8140 KB Output is correct
7 Correct 55 ms 8016 KB Output is correct
8 Correct 91 ms 8024 KB Output is correct
9 Correct 91 ms 8016 KB Output is correct
10 Correct 61 ms 8156 KB Output is correct
11 Correct 55 ms 8020 KB Output is correct
12 Correct 92 ms 8020 KB Output is correct
13 Correct 70 ms 8168 KB Output is correct
14 Correct 60 ms 8016 KB Output is correct
15 Correct 88 ms 8020 KB Output is correct
16 Incorrect 79 ms 8164 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 70 ms 8012 KB Output is correct
3 Correct 74 ms 8172 KB Output is correct
4 Correct 894 ms 78828 KB Output is correct
5 Correct 71 ms 8168 KB Output is correct
6 Correct 71 ms 8176 KB Output is correct
7 Correct 98 ms 8272 KB Output is correct
8 Correct 76 ms 8300 KB Output is correct
9 Correct 72 ms 8272 KB Output is correct
10 Correct 61 ms 8016 KB Output is correct
11 Correct 68 ms 8272 KB Output is correct
12 Correct 76 ms 8024 KB Output is correct
13 Correct 72 ms 8276 KB Output is correct
14 Correct 884 ms 78520 KB Output is correct
15 Incorrect 57 ms 8016 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

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