oj.uz

Submission #322568

# Submission time Handle Problem Language Result Execution time Memory
322568 2020-11-14T23:15:39 Z arbor Strange Device (APIO19_strange_device) C++17
65 / 100
 547 ms 53564 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 - 1);
    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 << '\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 1 ms 364 KB Output is correct
2 Correct 6 ms 1260 KB Output is correct
3 Correct 6 ms 1132 KB Output is correct
4 Correct 1 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 492 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 5 ms 1132 KB Output is correct
17 Correct 53 ms 5732 KB Output is correct
18 Correct 1 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 0 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 384 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 335 ms 41404 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 488 ms 53436 KB Output is correct
3 Correct 497 ms 53308 KB Output is correct
4 Correct 451 ms 53308 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 488 ms 53436 KB Output is correct
3 Correct 497 ms 53308 KB Output is correct
4 Correct 451 ms 53308 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 458 ms 53564 KB Output is correct
7 Correct 484 ms 53308 KB Output is correct
8 Correct 470 ms 53504 KB Output is correct
9 Correct 529 ms 53448 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 488 ms 53436 KB Output is correct
3 Correct 497 ms 53308 KB Output is correct
4 Correct 451 ms 53308 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 48 ms 5732 KB Output is correct
7 Correct 48 ms 5732 KB Output is correct
8 Correct 46 ms 5732 KB Output is correct
9 Correct 45 ms 5732 KB Output is correct
10 Correct 45 ms 5732 KB Output is correct
11 Correct 47 ms 5732 KB Output is correct
12 Correct 46 ms 5732 KB Output is correct
13 Correct 50 ms 5732 KB Output is correct
14 Correct 48 ms 5864 KB Output is correct
15 Correct 52 ms 5732 KB Output is correct
16 Correct 56 ms 5740 KB Output is correct
17 Correct 45 ms 5732 KB Output is correct
18 Correct 482 ms 53436 KB Output is correct
19 Correct 485 ms 53308 KB Output is correct
20 Correct 535 ms 53336 KB Output is correct
21 Correct 50 ms 5732 KB Output is correct
22 Correct 44 ms 5732 KB Output is correct
23 Correct 144 ms 18688 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 63 ms 5732 KB Output is correct
3 Correct 49 ms 5732 KB Output is correct
4 Correct 547 ms 53560 KB Output is correct
5 Correct 53 ms 5860 KB Output is correct
6 Correct 50 ms 5732 KB Output is correct
7 Correct 50 ms 5732 KB Output is correct
8 Correct 51 ms 5732 KB Output is correct
9 Correct 50 ms 5732 KB Output is correct
10 Correct 52 ms 5732 KB Output is correct
11 Correct 58 ms 6004 KB Output is correct
12 Correct 45 ms 5732 KB Output is correct
13 Correct 50 ms 5732 KB Output is correct
14 Correct 526 ms 53384 KB Output is correct
15 Correct 51 ms 5732 KB Output is correct
16 Correct 467 ms 53440 KB Output is correct
17 Correct 476 ms 53320 KB Output is correct
18 Correct 1 ms 364 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 6 ms 1260 KB Output is correct
3 Correct 6 ms 1132 KB Output is correct
4 Correct 1 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 492 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 5 ms 1132 KB Output is correct
17 Correct 53 ms 5732 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Incorrect 0 ms 364 KB Output isn't correct
21 Halted 0 ms 0 KB -