Submission #646055

#	Time	Username	Problem	Language	Result	Execution time	Memory
646055		Tenis0206	Strange Device (APIO19_strange_device)	C++11	100 / 100	747 ms	100276 KiB

strange_device

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

using namespace std;

int n,a,b;

vector<pair<int,int>> eves;

int gcd(int a, int b)
{
    int r = a % b;
    while(r)
    {
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    long long N,A,B;
    cin>>N>>A>>B;
    n = N;
    a = A;
    b = B;
    int div = a * b / gcd(b + 1, a);
    bool done = false;
    for(int i=1; i<=n; i++)
    {
        int l,r;
        long long L,R;
        cin>>L>>R;
        l = L;
        r = R;
        if(r - l + 1 >= div)
        {
            done = true;
        }
        l %= div;
        r %= div;
        if(l <= r)
        {
            eves.push_back({l,1});
            eves.push_back({r+1,-1});
        }
        else
        {
            eves.push_back({0,1});
            eves.push_back({r+1,-1});
            eves.push_back({l,1});
            eves.push_back({div,-1});
        }
    }
    if(done)
    {
        vector<short> r;
        while(div)
        {
            r.push_back(div % 10);
            div /= 10;
        }
        reverse(r.begin(),r.end());
        for(auto it : r)
        {
            cout<<it;
        }
        cout<<'\n';
        return 0;
    }
    sort(eves.begin(),eves.end());
    int nr = 0;
    int rez = 0;
    int last = 0;
    for(auto it : eves)
    {
        if(nr==0 && it.second==1)
        {
            last = it.first;
        }
        nr += it.second;
        if(nr==0 && it.second==-1)
        {
            rez += it.first - last;
        }
    }
    vector<short> r;
    while(rez)
    {
        r.push_back(rez % 10);
        rez /= 10;
    }
    reverse(r.begin(),r.end());
    for(auto it : r)
    {
        cout<<it;
    }
    cout<<'\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