Submission #783433

#	Time	Username	Problem	Language	Result	Execution time	Memory
783433		christinelynn	Strange Device (APIO19_strange_device)	C++17	10 / 100	550 ms	63004 KiB

strange_device

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

const int INFF = 2e18;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int n, a, b;
        cin >> n >> a >> b;

        /*
        0 0 0 0
        1 1 1 1
        2 2 2 2
        4 3 1 0
        5 4 2 1
        6 5 0 2
        8 6 2 0
        9 7 0 1
        10 8 1 2
        12 9 0 0

        0 0 0 0
        1 1 1 1
        2 2 0 2
        3 3 1 3
        5 4 1 0
        6 5 0 1
        7 6 1 2
        8 7 0 3
        10 8 0 0

        4 2

        0 0 0 0
        1 1 1 1
        3 2 3 0
        4 3 0 1
        6 4 2 0
        7 5 3 1
        9 6 1 2
        10 7 2 1
        12 8  0 0
        */

        set<pair<int, int>> seg;
        
        auto insert = [&](int l, int r) {
                auto it = seg.lower_bound({l, 0});
                if (!seg.empty() && it != seg.begin()) --it;

                int mnl = l, mxr = r;
                vector<pair<int, int>> del;

                for (; it != seg.end(); it++) {
                        if (it->fi > r) break;

                        if (it->fi < l && it->se >= l) {
                                del.push_back(*it);
                                mnl = min(mnl, it->fi);
                                mxr = max(mxr, it->se);
                        }

                        if (it->fi >= l && it->fi <= r) {
                                del.push_back(*it);
                                mnl = min(mnl, it->fi);
                                mxr = max(mxr, it->se);
                        }
                }

                for (auto p : del) seg.erase(p);

                seg.insert({mnl, mxr});
        };

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

                if (a <= INFF / b && r - l + 1 >= a * b) {
                        cout << a * b << '\n';
                        return 0;
                }
                
                if (a <= INFF / b) {
                        l %= a * b;
                        r %= a * b;
                }

                if (l <= r) {
                        insert(l, r);
                } else {
                        assert(a <= INFF / b);

                        insert(l, a * b - 1);
                        insert(0, r);
                }
        }
        
        int ans = 0;
        for (auto [l, r] : seg) ans += r - l + 1;

        cout << ans << '\n';

        return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 30