oj.uz

Submission #848251

# Submission time Handle Problem Language Result Execution time Memory
848251 2023-09-11T20:31:57 Z popovicirobert Strange Device (APIO19_strange_device) C++14
15 / 100
 882 ms 79080 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 = 3e18;

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 / b < a / __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 1116 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 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 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 0 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 356 KB Output is correct
2 Correct 702 ms 78952 KB Output is correct
3 Correct 744 ms 78724 KB Output is correct
4 Correct 773 ms 78560 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 356 KB Output is correct
2 Correct 702 ms 78952 KB Output is correct
3 Correct 744 ms 78724 KB Output is correct
4 Correct 773 ms 78560 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 714 ms 78572 KB Output is correct
7 Correct 728 ms 78672 KB Output is correct
8 Correct 717 ms 78688 KB Output is correct
9 Correct 882 ms 78776 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 356 KB Output is correct
2 Correct 702 ms 78952 KB Output is correct
3 Correct 744 ms 78724 KB Output is correct
4 Correct 773 ms 78560 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 56 ms 8152 KB Output is correct
7 Correct 55 ms 8016 KB Output is correct
8 Correct 57 ms 8016 KB Output is correct
9 Correct 72 ms 8268 KB Output is correct
10 Correct 57 ms 8372 KB Output is correct
11 Correct 58 ms 8184 KB Output is correct
12 Correct 59 ms 8176 KB Output is correct
13 Correct 65 ms 8016 KB Output is correct
14 Correct 57 ms 8168 KB Output is correct
15 Correct 78 ms 8272 KB Output is correct
16 Incorrect 77 ms 8276 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 68 ms 8040 KB Output is correct
3 Correct 78 ms 8384 KB Output is correct
4 Correct 782 ms 79080 KB Output is correct
5 Correct 71 ms 8264 KB Output is correct
6 Correct 75 ms 8228 KB Output is correct
7 Correct 81 ms 8232 KB Output is correct
8 Correct 72 ms 8068 KB Output is correct
9 Correct 68 ms 8016 KB Output is correct
10 Correct 64 ms 8272 KB Output is correct
11 Correct 65 ms 8016 KB Output is correct
12 Correct 64 ms 8172 KB Output is correct
13 Correct 70 ms 8016 KB Output is correct
14 Correct 852 ms 78860 KB Output is correct
15 Incorrect 62 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 1116 KB Output isn't correct
3 Halted 0 ms 0 KB -