oj.uz

Submission #216354

# Submission time Handle Problem Language Result Execution time Memory
216354 2020-03-27T07:45:35 Z usachevd0 Strange Device (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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -