제출 #216353

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
216353		usachevd0	이상한 기계 (APIO19_strange_device)	C++14	0 / 100	657 ms	33252 KiB

strange_device

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;

void debug_out()
{
    cerr << endl;
}

template<typename T1, typename... T2> void debug_out(T1 A, T2... B)
{
    cerr << ' ' << A;
    debug_out(B...);
}

#ifdef DEBUG
    #define time(...) 42
    #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
    #define debug(...) 42
#endif

template<typename T1, typename T2> bool chkmin(T1 &x, T2 y) { return y < x ? (x = y, true) : false; }
template<typename T1, typename T2> bool chkmax(T1 &x, T2 y) { return y > x ? (x = y, true) : false; }

ll gcd(ll a, ll b)
{
    for (; b; swap(a, b)) a %= b;
    return a;
}

signed main()
{
#ifdef DEBUG
    freopen("in", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    ll A, B;
    cin >> n >> A >> B;
    ll M1 = A / gcd(B + 1, A);
    ld temp = M1 * (ld)B;
    if (temp > 1000000000000000100LL)
    {
        ll sum = 0;
        while (n--)
        {
            ll l, r;
            cin >> l >> r;
            sum += r - l + 1;
        }
        cout << sum << '\n';
        exit(0);
    }
    ll M = M1 * B;
    vector<pll> ev;
    while (n--)
    {
        ll l, r;
        cin >> l >> r;
        if (r - l + 1 >= M)
        {
            cout << M << '\n';
            exit(0);
        }
        l %= M;
        r %= M;
        if (l <= r)
        {
            ev.emplace_back(l, 0);
            ev.emplace_back(r, 1);
        }
        else
        {
            ev.emplace_back(0, 0);
            ev.emplace_back(l, 1);
            ev.emplace_back(r, 0);
            ev.emplace_back(M - 1, 1);
        }
    }
    sort(all(ev));
    int cnt = 0;
    ll last = -1;
    ll ans = 0;
    for (auto &e : ev)
    {
        if (e.se == 1)
        {
            ++cnt;
            if (cnt == 1)
            {
                last = e.fi;
            }
        }
        else
        {
            --cnt;
            if (cnt == 0)
            {
                ans += e.fi - last + 1;
            }
        }
    }
    cout << ans << '\n';

    return 0;
}

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