oj.uz

Submission #216352

# Submission time Handle Problem Language Result Execution time Memory
216352 2020-03-27T07:39:54 Z usachevd0 Strange Device (APIO19_strange_device) C++14
10 / 100
 5000 ms 524292 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;
    set<ll> rem;
    while (n--)
    {
        ll l, r;
        cin >> l >> r;
        for (ll x = l; x <= r; ++x)
            rem.insert(x % M);
    }
    cout << rem.size() << '\n';

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 46 ms 9720 KB Output is correct
3 Correct 65 ms 13944 KB Output is correct
4 Correct 6 ms 768 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 9 ms 1024 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 34 ms 5376 KB Output is correct
16 Correct 26 ms 5496 KB Output is correct
17 Correct 67 ms 8696 KB Output is correct
18 Correct 4 ms 384 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Runtime error 3095 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 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 Correct 102 ms 24288 KB Output is correct
3 Correct 95 ms 24184 KB Output is correct
4 Correct 94 ms 23032 KB Output is correct
5 Execution timed out 5077 ms 47324 KB Time limit exceeded

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 641 ms 50884 KB Output is correct
3 Runtime error 2223 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 641 ms 50884 KB Output is correct
3 Runtime error 2223 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 641 ms 50884 KB Output is correct
3 Runtime error 2223 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
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 Runtime error 2216 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 46 ms 9720 KB Output is correct
3 Correct 65 ms 13944 KB Output is correct
4 Correct 6 ms 768 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 9 ms 1024 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 34 ms 5376 KB Output is correct
16 Correct 26 ms 5496 KB Output is correct
17 Correct 67 ms 8696 KB Output is correct
18 Correct 4 ms 384 KB Output is correct
19 Correct 4 ms 384 KB Output is correct
20 Runtime error 3095 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -