Submission #1068814

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068814		alexdd	이상한 기계 (APIO19_strange_device)	C++17	65 / 100	1391 ms	78676 KiB

strange_device

#include<bits/stdc++.h>
using namespace std;
#define int long long
int gcd(int x, int y)
{
    while(x>0)
    {
        int r = y%x;
        y=x;
        x=r;
    }
    return y;
}
set<pair<__int128,__int128>> s;
void baga(__int128 le, __int128 ri)
{
    if(s.empty())
    {
        s.insert({le,ri});
        return;
    }
    auto it = s.lower_bound({le+1,-1});
    if(it!=s.begin()) it--;
    while(it!=s.end())
    {
        if((*it).first > ri)
            break;
        else if((*it).second < le)
        {
            it++;
        }
        else
        {
            le = min(le, (*it).first);
            ri = max(ri, (*it).second);
            it = s.erase(it);
        }
    }
    s.insert({le,ri});
}
void afis(__int128 x)
{
    vector<int> cif;
    __int128 zece=10;
    while(x>0)
    {
        cif.push_back(x%zece);
        x/=zece;
    }
    reverse(cif.begin(),cif.end());
    for(auto c:cif) cout<<c;
}
signed main()
{
    int n,A,B;
    cin>>n>>A>>B;
    A = A / gcd(A,B+1);
    __int128 le,ri;

    __int128 copA=A,copB=B;
    __int128 prod=copA*copB;

    int cle,cri;
    for(int i=1;i<=n;i++)
    {
        cin>>cle>>cri;
        le=cle;
        ri=cri;
        if(le==ri)
        {
            baga(le%prod,le%prod);
            continue;
        }
        le = le%prod;
        ri = ri%prod;
        if(le<ri)
        {
            baga(le,ri);
        }
        else
        {
            baga(le,prod-1);
            baga(0,ri);
        }
    }
    __int128 cnt=0;
    for(auto it:s)
    {
        cnt += it.second-it.first+1;
    }
    afis(cnt);
    return 0;
}

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