Submission #1148673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148673		heeheeheehaaw	Strange Device (APIO19_strange_device)	C++20	100 / 100	1253 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 * (B + 1) / __gcd(b + 1, a) / (B + 1) * B;
    int cv = (int) CV;
    __int128 ct = 1000000000000000001;
    if(CV >= ct) cv = (int)ct;
    //cout<<cv<<'\n';
    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 - 1;
            if(tl > dr) tl = dr;
            if(tl - st + 1 == cv)
            {
                ok = true;
                break;
            }


            mp[st - cv * (st / cv)]++;
            if((tl + 1) % cv == 0) mp[cv]--;
            else mp[(tl + 1) - cv * ((tl + 1) / 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: 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