Submission #646046

#	Time	Username	Problem	Language	Result	Execution time	Memory
646046		Tenis0206	Strange Device (APIO19_strange_device)	C++11	35 / 100	628 ms	68964 KiB

strange_device

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

using namespace std;

int n,a,b;

vector<pair<int,int>> eves;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>a>>b;
    int div = a * b / __gcd(b + 1, a);
    bool done = false;
    for(int i=1;i<=n;i++)
    {
        int l,r;
        cin>>l>>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)
    {
        cout<<div<<'\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;
        }
    }
    cout<<rez<<'\n';
    return 0;
}

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