Submission #1143083

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143083		boris_mihov	Strange Device (APIO19_strange_device)	C++20	15 / 100	280 ms	32616 KiB

strange_device

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <set>

typedef long long llong;
const int MAXN = 1e6 + 10;
const llong INF = 1e18;

int n;
llong a, b;
llong l[MAXN];
llong r[MAXN];
std::vector <std::pair <llong, llong>> v;

void solve()
{
    llong aPrim = a / std::__gcd(a, b + 1);
    if (aPrim > INF / b)
    {
        llong sum = 0;
        for (int i = 1 ; i <= n ; ++i)
        {
            sum += r[i] - l[i] + 1;
        }

        std::cout << sum << '\n';
        return;
    } 

    llong s = aPrim * b;
    for (int i = 1 ; i <= n ; ++i)
    {
        if (r[i] - l[i] + 1 >= s)
        {
            std::cout << s << '\n';
            return;
        }

        if (l[i] % s <= r[i] % s)
        {
            v.push_back({l[i] % s, r[i] % s});
        } else
        {
            v.push_back({l[i] % s, s - 1});
            v.push_back({0, r[i] % s});
        }
    }

    llong sum = 0;
    llong last = -1;
    std::sort(v.begin(), v.end(), [&](auto x, auto y)
    {
        return x.second < y.second;
    });

    for (const auto &[l, r] : v)
    {
        sum += std::max(0LL, r - std::max(last, l - 1));
        last = std::max(last, r);
    }

    std::cout << sum << '\n';
}

void input()
{
    std::cin >> n >> a >> b;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> l[i] >> r[i];
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

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