oj.uz

Submission #216353

# Submission time Handle Problem Language Result Execution time Memory
216353 2020-03-27T07:43:47 Z usachevd0 Strange Device (APIO19_strange_device) C++14
0 / 100
 657 ms 33252 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 == 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.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Incorrect 10 ms 1024 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Incorrect 5 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 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

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Incorrect 657 ms 33252 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Incorrect 657 ms 33252 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Incorrect 657 ms 33252 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 79 ms 7272 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Incorrect 10 ms 1024 KB Output isn't correct
3 Halted 0 ms 0 KB -