Submission #1031815

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1031815	2024-07-23T07:39:03 Z	stdfloat	Strange Device (APIO19_strange_device)	C++17	35 / 100	582 ms	116800 KB

strange_device

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

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

    int n;
    ll A, B;
    cin >> n >> A >> B;

    map<ll, int> m;
    ll L = A / __gcd(A, B + 1) * B;
    while (n--) {
        ll l, r;
        cin >> l >> r;

        if (L <= r - l + 1) {
            m[0]++; m[L]--;
            continue;
        }

        m[l % L]++; m[r % L + 1]--;

        if (l % L > r % L) {
            m[0]++; m[L]--;
        }
    }

    vector<pair<ll, int>> v;
    for (auto i : m) v.push_back(i);

    int sm = 0;
    ll ans = 0;
    for (int i = 0; i + 1 < (int)v.size(); i++) {
        sm += v[i].second;
        ans += !!sm * (v[i + 1].first - v[i].first);
    }

    cout << ans << '\n';
}

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	4 ms	1812 KB	Output is correct
3	Correct	5 ms	1848 KB	Output is correct
4	Correct	1 ms	344 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	604 KB	Output is correct
9	Correct	1 ms	600 KB	Output is correct
10	Correct	1 ms	344 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	356 KB	Output is correct
16	Correct	4 ms	1764 KB	Output is correct
17	Correct	46 ms	10812 KB	Output is correct
18	Incorrect	0 ms	352 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #2
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	356 KB	Output is correct
2	Correct	0 ms	356 KB	Output is correct
3	Correct	1 ms	352 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Incorrect	0 ms	348 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	344 KB	Output is correct
2	Correct	1 ms	604 KB	Output is correct
3	Correct	1 ms	604 KB	Output is correct
4	Correct	1 ms	464 KB	Output is correct
5	Correct	153 ms	13008 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	487 ms	98300 KB	Output is correct
3	Correct	512 ms	116548 KB	Output is correct
4	Correct	579 ms	116564 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	487 ms	98300 KB	Output is correct
3	Correct	512 ms	116548 KB	Output is correct
4	Correct	579 ms	116564 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	495 ms	116580 KB	Output is correct
7	Correct	512 ms	116672 KB	Output is correct
8	Correct	492 ms	116660 KB	Output is correct
9	Correct	582 ms	116680 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	487 ms	98300 KB	Output is correct
3	Correct	512 ms	116548 KB	Output is correct
4	Correct	579 ms	116564 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	38 ms	12416 KB	Output is correct
7	Correct	43 ms	12484 KB	Output is correct
8	Correct	40 ms	12484 KB	Output is correct
9	Correct	43 ms	12488 KB	Output is correct
10	Correct	40 ms	12488 KB	Output is correct
11	Correct	41 ms	12580 KB	Output is correct
12	Correct	41 ms	12484 KB	Output is correct
13	Correct	74 ms	12484 KB	Output is correct
14	Correct	38 ms	12492 KB	Output is correct
15	Correct	57 ms	12484 KB	Output is correct
16	Correct	52 ms	12484 KB	Output is correct
17	Correct	46 ms	12520 KB	Output is correct
18	Correct	567 ms	116668 KB	Output is correct
19	Correct	546 ms	116708 KB	Output is correct
20	Correct	542 ms	116752 KB	Output is correct
21	Correct	41 ms	12384 KB	Output is correct
22	Correct	41 ms	12380 KB	Output is correct
23	Correct	72 ms	12968 KB	Output is correct

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	49 ms	12372 KB	Output is correct
3	Correct	49 ms	12404 KB	Output is correct
4	Correct	520 ms	116728 KB	Output is correct
5	Correct	49 ms	12512 KB	Output is correct
6	Correct	49 ms	12412 KB	Output is correct
7	Correct	50 ms	12488 KB	Output is correct
8	Correct	48 ms	12448 KB	Output is correct
9	Correct	57 ms	12488 KB	Output is correct
10	Correct	52 ms	12496 KB	Output is correct
11	Correct	50 ms	12472 KB	Output is correct
12	Correct	43 ms	12488 KB	Output is correct
13	Correct	48 ms	12484 KB	Output is correct
14	Correct	570 ms	116744 KB	Output is correct
15	Correct	42 ms	12596 KB	Output is correct
16	Correct	502 ms	116800 KB	Output is correct
17	Correct	554 ms	116756 KB	Output is correct
18	Incorrect	1 ms	344 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	4 ms	1812 KB	Output is correct
3	Correct	5 ms	1848 KB	Output is correct
4	Correct	1 ms	344 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	604 KB	Output is correct
9	Correct	1 ms	600 KB	Output is correct
10	Correct	1 ms	344 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	356 KB	Output is correct
16	Correct	4 ms	1764 KB	Output is correct
17	Correct	46 ms	10812 KB	Output is correct
18	Incorrect	0 ms	352 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Submission #1031815

Compilation message