oj.uz

Submission #322570

# Submission time Handle Problem Language Result Execution time Memory
322570 2020-11-14T23:23:28 Z arbor Strange Device (APIO19_strange_device) C++14
65 / 100
 620 ms 17108 KB 
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int MN = 1e5 + 5;
using ull = unsigned long long;

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    ull n, a, b; cin >> n >> a >> b;
    ull p = a / __gcd(a, b + 1) * b;
    vector<pair<ull, ull>> v;
    for (int i = 0; i < n; i++) {
        ull l, r; cin >> l >> r;
        l %= p, r %= p;
        if (l > r) v.emplace_back(0, r), v.emplace_back(l, p - 1);
        else v.emplace_back(l, r);
    }
    v.emplace_back(p, p);
    sort(all(v));
    ull ans = 0;
    for (int i = 0; i < v.size();) {
        int j = i;
        for (; v[i].second >= v[j].second && j < v.size(); j++);
        ans += v[i].second - v[i].first + 1;
        v[j].first = max(v[j].first, v[i].second + 1);
        i = j;
    }
    cout << ans - 1 << '\n';
    return 0;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:14:23: warning: comparison of integer expressions of different signedness: 'int' and 'ull' {aka 'long long unsigned int'} [-Wsign-compare]
   14 |     for (int i = 0; i < n; i++) {
      |                     ~~^~~
strange_device.cpp:23:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long unsigned int, long long unsigned int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for (int i = 0; i < v.size();) {
      |                     ~~^~~~~~~~~~
strange_device.cpp:25:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long unsigned int, long long unsigned int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for (; v[i].second >= v[j].second && j < v.size(); j++);
      |                                              ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 7 ms 748 KB Output is correct
3 Correct 6 ms 876 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 0 ms 364 KB Output is correct
11 Correct 0 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 0 ms 364 KB Output is correct
14 Correct 0 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 6 ms 748 KB Output is correct
17 Correct 59 ms 2536 KB Output is correct
18 Correct 0 ms 364 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 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 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 394 ms 17108 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 547 ms 16976 KB Output is correct
3 Correct 578 ms 16848 KB Output is correct
4 Correct 517 ms 17000 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 547 ms 16976 KB Output is correct
3 Correct 578 ms 16848 KB Output is correct
4 Correct 517 ms 17000 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 529 ms 16848 KB Output is correct
7 Correct 547 ms 16848 KB Output is correct
8 Correct 542 ms 16868 KB Output is correct
9 Correct 598 ms 16848 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 547 ms 16976 KB Output is correct
3 Correct 578 ms 16848 KB Output is correct
4 Correct 517 ms 17000 KB Output is correct
5 Correct 1 ms 268 KB Output is correct
6 Correct 53 ms 2536 KB Output is correct
7 Correct 54 ms 2536 KB Output is correct
8 Correct 55 ms 2536 KB Output is correct
9 Correct 52 ms 2536 KB Output is correct
10 Correct 53 ms 2536 KB Output is correct
11 Correct 59 ms 2692 KB Output is correct
12 Correct 54 ms 2672 KB Output is correct
13 Correct 55 ms 2536 KB Output is correct
14 Correct 53 ms 2536 KB Output is correct
15 Correct 58 ms 2536 KB Output is correct
16 Correct 59 ms 2536 KB Output is correct
17 Correct 52 ms 2684 KB Output is correct
18 Correct 549 ms 17000 KB Output is correct
19 Correct 564 ms 16848 KB Output is correct
20 Correct 597 ms 17108 KB Output is correct
21 Correct 57 ms 2568 KB Output is correct
22 Correct 59 ms 2576 KB Output is correct
23 Correct 170 ms 8836 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 56 ms 2536 KB Output is correct
3 Correct 56 ms 2536 KB Output is correct
4 Correct 620 ms 16976 KB Output is correct
5 Correct 56 ms 2536 KB Output is correct
6 Correct 55 ms 2536 KB Output is correct
7 Correct 56 ms 2536 KB Output is correct
8 Correct 58 ms 2536 KB Output is correct
9 Correct 56 ms 2536 KB Output is correct
10 Correct 56 ms 2536 KB Output is correct
11 Correct 65 ms 2536 KB Output is correct
12 Correct 58 ms 2536 KB Output is correct
13 Correct 57 ms 2536 KB Output is correct
14 Correct 586 ms 16976 KB Output is correct
15 Correct 56 ms 2536 KB Output is correct
16 Correct 532 ms 16848 KB Output is correct
17 Correct 543 ms 16848 KB Output is correct
18 Correct 0 ms 364 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 7 ms 748 KB Output is correct
3 Correct 6 ms 876 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 0 ms 364 KB Output is correct
11 Correct 0 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 0 ms 364 KB Output is correct
14 Correct 0 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 6 ms 748 KB Output is correct
17 Correct 59 ms 2536 KB Output is correct
18 Correct 0 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Incorrect 1 ms 364 KB Output isn't correct
21 Halted 0 ms 0 KB -