oj.uz

Submission #128168

# Submission time Handle Problem Language Result Execution time Memory
128168 2019-07-10T13:31:01 Z wasyl Strange Device (APIO19_strange_device) C++11
35 / 100
 685 ms 18276 KB 
#include <bits/stdc++.h>
#define st first
#define nd second
using namespace std;
using ll = long long;

int n; ll a, b, v, m;
vector< pair< ll, ll > > ilo;

ll gcd(const ll a, const ll b)
{
    return (b == 0? a : gcd(b, a % b));
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> a >> b;

    v = gcd(a, b + 1);
    __int128 q = a / v * b;
    if (q >= (ll)(1e18) + 1) m = (ll)(1e18) + 1;
    else m = q;

    //cerr << "m: " << m << '\n';

    for (int i = 0; i < n; ++i)
    {
        ll l, r; cin >> l >> r;
        if (r - l + 1 >= m)
            return cout << m << '\n', 0;
        r %= m; l %= m;
        if (l > r) 
            ilo.push_back({l, m - 1}), ilo.push_back({0, r});
        else
            ilo.push_back({l, r});
    }

    sort(begin(ilo), end(ilo));

    //for (int i = 0; i < ilo.size(); ++i)
        //cerr << ilo[i].st << ' ' << ilo[i].nd << '\n';

    ll c = 0, p = -1;
    for (int i = 0; i < ilo.size(); ++i)
    {
        //cerr << p << ' ' << ilo[i].st << ' ' << ilo[i].nd << ' ';
        c += (max(0ll, ilo[i].nd - max(ilo[i].st - 1, p))), p = max(p, ilo[i].nd);
        //cerr << c << '\n';
    }

    cout << c << '\n';
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:47:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < ilo.size(); ++i)
                     ~~^~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 8 ms 1016 KB Output is correct
3 Correct 8 ms 1044 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 404 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 9 ms 1144 KB Output is correct
17 Correct 68 ms 4208 KB Output is correct
18 Incorrect 2 ms 376 KB Output isn't correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Incorrect 2 ms 376 KB Output isn't correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 396 KB Output is correct
5 Correct 449 ms 18276 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 614 ms 17800 KB Output is correct
3 Correct 608 ms 17624 KB Output is correct
4 Correct 601 ms 17612 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 614 ms 17800 KB Output is correct
3 Correct 608 ms 17624 KB Output is correct
4 Correct 601 ms 17612 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 601 ms 17584 KB Output is correct
7 Correct 606 ms 17576 KB Output is correct
8 Correct 603 ms 17636 KB Output is correct
9 Correct 684 ms 17620 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 614 ms 17800 KB Output is correct
3 Correct 608 ms 17624 KB Output is correct
4 Correct 601 ms 17612 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 62 ms 3984 KB Output is correct
7 Correct 66 ms 3824 KB Output is correct
8 Correct 62 ms 3824 KB Output is correct
9 Correct 65 ms 3816 KB Output is correct
10 Correct 63 ms 3900 KB Output is correct
11 Correct 65 ms 3824 KB Output is correct
12 Correct 63 ms 3820 KB Output is correct
13 Correct 68 ms 3824 KB Output is correct
14 Correct 62 ms 3824 KB Output is correct
15 Correct 69 ms 3824 KB Output is correct
16 Correct 67 ms 3788 KB Output is correct
17 Correct 65 ms 3864 KB Output is correct
18 Correct 610 ms 17860 KB Output is correct
19 Correct 610 ms 17452 KB Output is correct
20 Correct 666 ms 17492 KB Output is correct
21 Correct 68 ms 3836 KB Output is correct
22 Correct 61 ms 3824 KB Output is correct
23 Correct 194 ms 10948 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 420 KB Output is correct
2 Correct 67 ms 3820 KB Output is correct
3 Correct 69 ms 3412 KB Output is correct
4 Correct 685 ms 17460 KB Output is correct
5 Correct 68 ms 3604 KB Output is correct
6 Correct 68 ms 3564 KB Output is correct
7 Correct 70 ms 3564 KB Output is correct
8 Correct 68 ms 3312 KB Output is correct
9 Correct 66 ms 3320 KB Output is correct
10 Correct 67 ms 3316 KB Output is correct
11 Correct 67 ms 3408 KB Output is correct
12 Correct 60 ms 3304 KB Output is correct
13 Correct 67 ms 3312 KB Output is correct
14 Correct 657 ms 17308 KB Output is correct
15 Correct 66 ms 3312 KB Output is correct
16 Correct 607 ms 17260 KB Output is correct
17 Correct 596 ms 17356 KB Output is correct
18 Incorrect 3 ms 376 KB Output isn't correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 8 ms 1016 KB Output is correct
3 Correct 8 ms 1044 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 404 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 9 ms 1144 KB Output is correct
17 Correct 68 ms 4208 KB Output is correct
18 Incorrect 2 ms 376 KB Output isn't correct