Submission #783438

#	Time	Username	Problem	Language	Result	Execution time	Memory
783438		makanhulia	이상한 기계 (APIO19_strange_device)	C++17	10 / 100	562 ms	62920 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

        4 1
        0 0
        2 1
        4 2

        3 2
        0 0
        1 1
        3 2
        4 3
        6 3

        3 1

        0 0
        2 1
        4 2
        6 3


        setiap b, nambah b + 1


        */

        int len = lcm(a, b + 1) / (b + 1) * b;

        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;
}

Compilation message (stderr)

strange_device.cpp: In function 'int32_t main()':
strange_device.cpp:77:13: warning: unused variable 'len' [-Wunused-variable]
   77 |         int len = lcm(a, b + 1) / (b + 1) * b;
      |             ^~~

• 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