oj.uz

Submission #848248

# Submission time Handle Problem Language Result Execution time Memory
848248 2023-09-11T20:24:23 Z popovicirobert Strange Device (APIO19_strange_device) C++14
15 / 100
 1085 ms 116228 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 = 1e18;

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 0 ms 344 KB Output is correct
2 Incorrect 6 ms 1464 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 504 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 452 KB Output is correct
5 Correct 0 ms 456 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 500 KB Output is correct
2 Incorrect 1 ms 348 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 1 ms 456 KB Output is correct
2 Correct 716 ms 116124 KB Output is correct
3 Correct 738 ms 115664 KB Output is correct
4 Correct 805 ms 115800 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 456 KB Output is correct
2 Correct 716 ms 116124 KB Output is correct
3 Correct 738 ms 115664 KB Output is correct
4 Correct 805 ms 115800 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 704 ms 115900 KB Output is correct
7 Correct 726 ms 116052 KB Output is correct
8 Correct 705 ms 115936 KB Output is correct
9 Correct 1085 ms 115736 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 456 KB Output is correct
2 Correct 716 ms 116124 KB Output is correct
3 Correct 738 ms 115664 KB Output is correct
4 Correct 805 ms 115800 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 55 ms 11856 KB Output is correct
7 Correct 55 ms 11856 KB Output is correct
8 Correct 57 ms 11856 KB Output is correct
9 Correct 75 ms 11860 KB Output is correct
10 Correct 59 ms 11860 KB Output is correct
11 Correct 56 ms 11864 KB Output is correct
12 Correct 62 ms 11860 KB Output is correct
13 Correct 67 ms 11880 KB Output is correct
14 Correct 57 ms 11856 KB Output is correct
15 Correct 80 ms 11992 KB Output is correct
16 Incorrect 82 ms 11856 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 348 KB Output is correct
2 Correct 73 ms 11744 KB Output is correct
3 Correct 74 ms 11748 KB Output is correct
4 Correct 850 ms 115936 KB Output is correct
5 Correct 90 ms 11972 KB Output is correct
6 Correct 95 ms 11856 KB Output is correct
7 Correct 89 ms 12044 KB Output is correct
8 Correct 86 ms 11948 KB Output is correct
9 Correct 68 ms 11872 KB Output is correct
10 Correct 66 ms 12284 KB Output is correct
11 Correct 62 ms 11856 KB Output is correct
12 Correct 62 ms 11744 KB Output is correct
13 Correct 72 ms 11852 KB Output is correct
14 Correct 866 ms 116228 KB Output is correct
15 Incorrect 63 ms 11956 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

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