oj.uz

Submission #398370

# Submission time Handle Problem Language Result Execution time Memory
398370 2021-05-04T08:15:55 Z jack715 Strange Device (APIO19_strange_device) C++14
65 / 100
 548 ms 25808 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pp pop_back
#define mp make_pair
#define bb back
#define ff first
#define ss second
#define int long long

using namespace std;

/*
 ____     __    _______    _______   __________
|     \  |  |  |  _____|  /  _____) |____  ____|
|  |\  \ |  |  | |__     (  (_____      |  |
|  | \  \|  |  |  __|     \_____  \     |  | 
|  |  \     |  | |_____    _____)  )    |  | 
|__|   \____|  |_______|  (_______/     |__| 
*/

int INF = LLONG_MAX;

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, A, B, I, gcd, k, l, r;
    cin >> n >> A >> B;
    gcd = __gcd(A, B+1);

    if (gcd == 1)
        k = A;
    else 
        k = A / gcd;

    if (INF / k <= B) 
        I = INF;
    else 
        I = k*B;

    // cout << I << '\n';
    vector<pair<int, int> > rem;

    for (int i = 0; i < n; i++) {
        cin >> l >> r;
        // cout << "input choice: " << l << ' ' << r << '\n';
        if (r-l >= I) {
            // cout << "choice 1\n";
            rem.pb({0, I});
        } else if (l%I > r%I) {
            // cout << "choice 2\n";
            rem.pb({l%I, I-1});
            rem.pb({0, r%I});
        } else {
            // cout << "choice 3\n";
            rem.pb({l%I, r%I});
        } 
    }

    int L = 0, ans = 0;
    sort(rem.begin(), rem.end());
    for (auto el : rem) {
        // cout << "el: " << el.ff << ' ' << el.ss << '\n';
        el.ff = max(el.ff, L);
        if (el.ff > el.ss)
            continue;
        ans += el.ss-el.ff+1;
        L = max(L, el.ss+1);
    }
    cout << ans << '\n';
    return 0;
}

/* stuff you should look for
    * int overflow, array bounds
    * special cases (n=1?)
    * do smth instead of nothing and stay organized
    * WRITE STUFF DOWN
    * DON'T GET STUCK ON ONE APPROACH
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 5 ms 844 KB Output is correct
3 Correct 6 ms 844 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 260 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 5 ms 884 KB Output is correct
17 Correct 53 ms 2796 KB Output is correct
18 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 368 KB Output is correct
5 Correct 345 ms 17124 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 509 ms 17512 KB Output is correct
3 Correct 447 ms 17448 KB Output is correct
4 Correct 443 ms 20368 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 509 ms 17512 KB Output is correct
3 Correct 447 ms 17448 KB Output is correct
4 Correct 443 ms 20368 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 455 ms 25808 KB Output is correct
7 Correct 453 ms 17108 KB Output is correct
8 Correct 455 ms 17348 KB Output is correct
9 Correct 548 ms 21668 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 509 ms 17512 KB Output is correct
3 Correct 447 ms 17448 KB Output is correct
4 Correct 443 ms 20368 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 44 ms 2684 KB Output is correct
7 Correct 48 ms 2688 KB Output is correct
8 Correct 45 ms 2680 KB Output is correct
9 Correct 45 ms 2752 KB Output is correct
10 Correct 44 ms 2708 KB Output is correct
11 Correct 46 ms 2680 KB Output is correct
12 Correct 43 ms 2640 KB Output is correct
13 Correct 46 ms 2752 KB Output is correct
14 Correct 44 ms 2792 KB Output is correct
15 Correct 50 ms 2756 KB Output is correct
16 Correct 47 ms 2724 KB Output is correct
17 Correct 44 ms 2664 KB Output is correct
18 Correct 461 ms 18220 KB Output is correct
19 Correct 444 ms 18340 KB Output is correct
20 Correct 496 ms 17644 KB Output is correct
21 Correct 59 ms 2760 KB Output is correct
22 Correct 43 ms 2672 KB Output is correct
23 Correct 139 ms 8904 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 48 ms 4676 KB Output is correct
3 Correct 48 ms 4408 KB Output is correct
4 Correct 523 ms 17812 KB Output is correct
5 Correct 49 ms 3516 KB Output is correct
6 Correct 52 ms 4164 KB Output is correct
7 Correct 47 ms 4260 KB Output is correct
8 Correct 48 ms 4408 KB Output is correct
9 Correct 47 ms 4496 KB Output is correct
10 Correct 48 ms 4336 KB Output is correct
11 Correct 48 ms 4016 KB Output is correct
12 Correct 43 ms 4408 KB Output is correct
13 Correct 48 ms 4428 KB Output is correct
14 Correct 528 ms 23392 KB Output is correct
15 Correct 48 ms 4540 KB Output is correct
16 Correct 444 ms 21052 KB Output is correct
17 Correct 448 ms 22528 KB Output is correct
18 Correct 1 ms 204 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 5 ms 844 KB Output is correct
3 Correct 6 ms 844 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 260 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 5 ms 884 KB Output is correct
17 Correct 53 ms 2796 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Incorrect 1 ms 204 KB Output isn't correct
21 Halted 0 ms 0 KB -