Submission #568944

#	Time	Username	Problem	Language	Result	Execution time	Memory
568944		four_specks	Strange Device (APIO19_strange_device)	C++17	100 / 100	517 ms	40456 KiB

strange_device

#include <bits/stdc++.h>

using namespace std;

inline namespace
{
} // namespace

void solve()
{
    int n;
    long a, b;
    cin >> n >> a >> b;

    vector<array<long, 2>> v(n);
    for (auto &[x, y] : v)
        cin >> x >> y, ++y;

    if (LONG_MAX / a / b)
    {
        long c = a * b / gcd(a, b + 1);

        vector<array<long, 2>> u;
        for (auto [x, y] : v)
        {
            if (y - x >= c)
                u.push_back({0, c});
            else
            {
                x %= c, y %= c;
                if (x < y)
                    u.push_back({x, y});
                else
                    u.push_back({x, c}), u.push_back({0, y});
            }
        }
        sort(u.begin(), u.end());

        long cnt = 0;

        long d = 0;
        for (auto [x, y] : u)
        {
            if (y > d)
            {
                cnt += y - max(x, d);
                d = y;
            }
        }

        cout << cnt << '\n';
    }
    else
    {
        long cnt = 0;
        for (auto [x, y] : v)
            cnt += y - x;

        cout << cnt << '\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);

    solve();

    return 0;
}

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