Submission #1148655

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148655		heeheeheehaaw	Strange Device (APIO19_strange_device)	C++20	40 / 100	1312 ms	63060 KiB

strange_device

#include <bits/stdc++.h>
#define int long long

using namespace std;

signed main()
{
    int n, a, b;
    cin>>n>>a>>b;
    __int128 A = a, B = b;
    __int128 CV = A / __gcd(b + 1, a) * B;
    int cv = (int) CV;
    __int128 ct = 1000000000000000000;
    if(CV >= ct) cv = (int)ct;

    map<int, int> mp;
    bool ok = false;
    for(int i = 1; i <= n; i++)
    {
        int st, dr;
        cin>>st>>dr;
        int cntupd = 0;
        while(st <= dr && !ok)
        {
            int tl = st - st % cv + cv;
            if(st % cv == 0) tl = st;

            if(tl > dr) tl = dr;
            if(tl - st + 1 == cv)
            {
                ok = true;
                break;
            }


            mp[st - cv * ((st - 1) / cv)]++;
            if(tl % cv == 0) mp[cv + 1]--;
            else mp[(tl + 1) - cv * (tl / cv)]--;
            st = tl + 1;
        }
    }

    if(ok)
    {
        cout<<cv;
        return 0;
    }

    int currsum = 0;
    int st = -1, rez = 0;
    for(auto it : mp)
    {
        currsum += it.second;
        assert(currsum >= 0);
        if(currsum > 0 && st == -1)
            st = it.first;
        else if(currsum == 0 && st != -1)
            rez += it.first - st, st = -1;
    }

    assert(st == -1);
    cout<<rez;
    return 0;
}

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