Submission #443239

#	Time	Username	Problem	Language	Result	Execution time	Memory
443239		Lam_lai_cuoc_doi	Strange Device (APIO19_strange_device)	C++17	100 / 100	589 ms	53416 KiB

strange_device

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

constexpr bool typetest = 0;
constexpr int N = 1e6 + 5;
constexpr ll Inf = 1e18 + 7;
int n;
ll A, B;
vector<pair<ll, ll>> s;

void Read()
{
    cin >> n >> A >> B;
    // A * B / gcd(A, B + 1)
    A /= __gcd(A, B + 1);
    if (A <= Inf / B)
        A *= B;
    else
        A = Inf;

    for (int i = 1; i <= n; ++i)
    {
        ll l, r;
        cin >> l >> r;
        if (r - l + 1 >= A)
            tie(l, r) = make_tuple(0, A - 1);
        else
        {
            l %= A;
            r %= A;
        }

        if (l <= r)
            s.emplace_back(l, r);
        else
        {
            s.emplace_back(l, A - 1);
            s.emplace_back(0, r);
        }
    }
}

void Solve()
{
    sort(s.begin(), s.end());
    ll leftest(0);

    ll ans(0);

    for (auto i : s)
    {
        leftest = max(leftest, i.first);
        ans += max(0ll, i.second - leftest + 1);
        leftest = max(leftest, i.second + 1);
    }

    cout << ans;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        Read();
        Solve();
    }
}

• 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