Submission #445171

#	Time	Username	Problem	Language	Result	Execution time	Memory
445171		benedict0724	Strange Device (APIO19_strange_device)	C++17	100 / 100	596 ms	59208 KiB

strange_device

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

vector<pair<ll, ll>> v1, v2;

ll gcd(ll x, ll y)
{
    if(y == 0) return x;
    return gcd(y, x%y);
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL);
    ll n, A, B; cin >> n >> A >> B;
    ll T = 1e18, S, G;
    G = gcd(A, B+1); A /= G;
    if(T/A >= B) S = A * B;
    else S = 1e18 + 7;

    //cout << S << "\n";

    for(int i=1;i<=n;i++)
    {
        ll l, r; cin >> l >> r;
        if(r - l + 1 >= S)
        {
            v1.push_back({0, S-1});
            continue;
        }
        l %= S, r %= S;
        if(l <= r) v1.push_back({l, r});
        else
        {
            v1.push_back({l, S-1});
            v1.push_back({0, r});
        }
    }

    sort(v1.begin(), v1.end());

    int m = v1.size();
    if(m == 1) v2.push_back(v1[0]);
    for(ll i=1,s=v1[0].first,e=v1[0].second;i<m;i++)
    {
        if(v1[i].first <= e) e = max(v1[i].second, e);
        else
        {
            v2.push_back({s, e});
            s = v1[i].first;
            e = v1[i].second;
        }

        if(i == m-1)
            v2.push_back({s, e});
    }

    m = v2.size();
    ll ans = 0;
    for(int i=0;i<m;i++)
        ans += v2[i].second - v2[i].first + 1;

    cout << ans;
}

• 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