oj.uz

Submission #564186

# Submission time Handle Problem Language Result Execution time Memory
564186 2022-05-18T16:56:27 Z hoanghq2004 Strange Device (APIO19_strange_device) C++14
35 / 100
 614 ms 35456 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    int n;
    long long A, B;
    vector <pair <long long, int> > events;
    cin >> n >> A >> B;
    long long T = A / __gcd(A, B + 1) * B;
    for (int i = 0; i < n; ++i) {
        long long L, R;
        cin >> L >> R;
        if (R - L + 1 >= T) {
            cout << T << '\n';
            exit(0);
        }
        L %= T, R %= T;
        if (L <= R) {
            events.push_back({L, 1});
            events.push_back({R + 1, -1});
        } else {
            events.push_back({L, 1});
            events.push_back({T, -1});
            events.push_back({0, 1});
            events.push_back({R + 1, -1});
        }
    }

    sort(events.begin(), events.end());
    int cur = 0;
    long long ans = 0;
    for (int i = 0; i + 1 < events.size(); ++i) {
        cur += events[i].second;
        if (cur != 0) ans += events[i + 1].first - events[i].first;
    }
    cout << ans;
}

Compilation message

strange_device.cpp: In function 'int main()':
strange_device.cpp:42:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (int i = 0; i + 1 < events.size(); ++i) {
      |                     ~~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 6 ms 1232 KB Output is correct
3 Correct 6 ms 1240 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 328 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 6 ms 1292 KB Output is correct
17 Correct 62 ms 7268 KB Output is correct
18 Incorrect 1 ms 212 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Incorrect 1 ms 316 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 344 ms 34996 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 490 ms 34708 KB Output is correct
3 Correct 497 ms 33268 KB Output is correct
4 Correct 470 ms 34016 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 490 ms 34708 KB Output is correct
3 Correct 497 ms 33268 KB Output is correct
4 Correct 470 ms 34016 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 495 ms 34072 KB Output is correct
7 Correct 489 ms 33536 KB Output is correct
8 Correct 493 ms 33804 KB Output is correct
9 Correct 567 ms 33244 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 490 ms 34708 KB Output is correct
3 Correct 497 ms 33268 KB Output is correct
4 Correct 470 ms 34016 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 48 ms 6160 KB Output is correct
7 Correct 54 ms 6084 KB Output is correct
8 Correct 51 ms 6084 KB Output is correct
9 Correct 49 ms 6084 KB Output is correct
10 Correct 49 ms 6084 KB Output is correct
11 Correct 50 ms 6004 KB Output is correct
12 Correct 50 ms 7236 KB Output is correct
13 Correct 58 ms 7224 KB Output is correct
14 Correct 48 ms 7368 KB Output is correct
15 Correct 57 ms 7292 KB Output is correct
16 Correct 55 ms 7236 KB Output is correct
17 Correct 50 ms 7256 KB Output is correct
18 Correct 504 ms 33812 KB Output is correct
19 Correct 476 ms 35224 KB Output is correct
20 Correct 599 ms 35456 KB Output is correct
21 Correct 58 ms 7300 KB Output is correct
22 Correct 46 ms 7228 KB Output is correct
23 Correct 150 ms 20820 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 53 ms 6144 KB Output is correct
3 Correct 57 ms 6320 KB Output is correct
4 Correct 614 ms 33300 KB Output is correct
5 Correct 50 ms 6212 KB Output is correct
6 Correct 54 ms 6204 KB Output is correct
7 Correct 52 ms 6128 KB Output is correct
8 Correct 55 ms 6160 KB Output is correct
9 Correct 53 ms 6148 KB Output is correct
10 Correct 55 ms 6212 KB Output is correct
11 Correct 52 ms 6208 KB Output is correct
12 Correct 49 ms 6124 KB Output is correct
13 Correct 55 ms 6192 KB Output is correct
14 Correct 567 ms 34956 KB Output is correct
15 Correct 56 ms 6208 KB Output is correct
16 Correct 465 ms 34980 KB Output is correct
17 Correct 485 ms 35012 KB Output is correct
18 Incorrect 0 ms 212 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 6 ms 1232 KB Output is correct
3 Correct 6 ms 1240 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 328 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 6 ms 1292 KB Output is correct
17 Correct 62 ms 7268 KB Output is correct
18 Incorrect 1 ms 212 KB Output isn't correct
19 Halted 0 ms 0 KB -