oj.uz

답안 #216354

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
216354 2020-03-27T07:45:35 Z usachevd0 이상한 기계 (APIO19_strange_device) C++14
5 / 100
 816 ms 45796 KB 
#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 == 0)
        {
            ++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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 10 ms 1024 KB Output is correct
3 Incorrect 11 ms 1024 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct

Subtask #3
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 661 ms 33472 KB Output is correct
3 Incorrect 673 ms 45760 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 661 ms 33472 KB Output is correct
3 Incorrect 673 ms 45760 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 661 ms 33472 KB Output is correct
3 Incorrect 673 ms 45760 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 71 ms 4548 KB Output is correct
3 Correct 72 ms 7272 KB Output is correct
4 Correct 816 ms 45796 KB Output is correct
5 Correct 73 ms 7272 KB Output is correct
6 Correct 74 ms 7276 KB Output is correct
7 Correct 79 ms 7276 KB Output is correct
8 Correct 77 ms 7276 KB Output is correct
9 Correct 75 ms 7276 KB Output is correct
10 Correct 79 ms 7272 KB Output is correct
11 Correct 72 ms 7276 KB Output is correct
12 Incorrect 79 ms 7276 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 10 ms 1024 KB Output is correct
3 Incorrect 11 ms 1024 KB Output isn't correct
4 Halted 0 ms 0 KB -