Submission #264097

#	Time	Username	Problem	Language	Result	Execution time	Memory
264097		batmendbar	Strange Device (APIO19_strange_device)	C++14	100 / 100	706 ms	50416 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;

const long long N = ((long long)1e18) + 5;

long long gcd(long long x, long long y)
{
    if (x < y)
        swap(x, y);
    while (y)
    {
        x %= y;
        swap(x, y);
    }
    return x;
}

vector<pair<long long, long long>> v;

long long ans;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    long long n, a, b;
    cin >> n >> a >> b;
    long long aa = a / gcd(a, b + 1);
    long long len;
    if (aa > (N / b))
        len = N;
    else
        len = aa * b;
    for (long long i = 0; i < n; i++)
    {
        long long bg, en;
        cin >> bg >> en;
        if (en - bg >= len)
        {
            cout << len << '\n';
            exit(0);
        }
        bg %= len;
        en %= len;
        if (bg > en)
        {
            v.push_back(make_pair(bg, len - 1));
            v.push_back(make_pair(0, en));
        }
        else
        {
            v.push_back(make_pair(bg, en));
        }
    }
    sort(v.begin(), v.end());
    long long bg = 0, en = -1;
    for (pair<long long, long long> x : v)
    {
        long long bgg = x.first;
        long long enn = x.second;
        if (bgg > en)
        {
            ans += en - bg + 1;
            bg = bgg;
            en = enn;
            continue;
        }
        if (bgg <= en)
        {
            en = max(en, enn);
        }
    }
    ans += en - bg + 1;
    cout << ans << '\n';
}

• 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