Submission #465484

#	Time	Username	Problem	Language	Result	Execution time	Memory
465484		alextodoran	Strange Device (APIO19_strange_device)	C++17	100 / 100	1088 ms	100156 KiB

strange_device

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll INF = LLONG_MAX / 2;

ll gcd (const ll &a, const ll &b)
{
    if(b == 0)
        return a;
    return gcd(b, a % b);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    ll A, B;
    cin >> n >> A >> B;

    ll per = A / gcd(B + 1, A);
    if(INF / per < B)
        per = INF;
    else
        per *= B;

    map <ll, int> mars;

    function <void (ll, ll)> proc = [&] (ll l, ll r)
    {
        if(r - l + 1 >= per)
            mars[0]++;
        else
        {
            l %= per;
            r %= per;
            if(l <= r)
            {
                mars[l]++;
                mars[r + 1]--;
            }
            else
            {
                mars[l]++;
                mars[per]--;

                mars[0]++;
                mars[r + 1]--;
            }
        }
    };

    for(int i = 0; i < n; i++)
    {
        ll l, r;
        cin >> l >> r;

        proc(l, r);
    }

    mars[per] = 0;

    ll answer = 0;
    int sum = 0;
    ll pr = 0;

    for(pair <ll, int> x : mars)
    {
        if(sum > 0)
            answer += x.first - pr;
        sum += x.second;
        pr = x.first;
    }

    cout << answer << "\n";

    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