Submission #1068799

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068799		alexdd	Strange Device (APIO19_strange_device)	C++17	65 / 100	1351 ms	115796 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;
        if((*it).second < le)
        {
            it++;
        }
        else if((*it).first <= le && (*it).second >= ri)
        {
            return;
        }
        else
        {
            le = min(le, (*it).first);
            ri = max(ri, (*it).second);
            it = s.erase(it);
        }
    }
    s.insert({le,ri});
}
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);
        }
    }
    int cnt=0;
    for(auto it:s)
    {
        cnt += it.second-it.first+1;
    }
    cout<<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