답안 #407022

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
407022	2021-05-18T11:10:42 Z	tengiz05	이상한 기계 (APIO19_strange_device)	C++17	35 / 100	1584 ms	60816 KB

strange_device

#include <bits/stdc++.h>
using i64 = long long;
constexpr i64 inf = 2e18 + 100;
int main(){
    i64 n, A, B;
    std::cin >> n >> A >> B;
    i64 gcd = std::__gcd(A, B + 1);
    i64 cycle = A / gcd;
    if (inf / gcd < B) {
        cycle = inf;
    } else {
        cycle *= B;
    }
    std::vector<std::pair<i64, i64>> v;
    for (int i = 0; i < n; i++) {
        i64 l, r;
        std::cin >> l >> r;
        l %= cycle;
        r %= cycle;
        if (r - l + 1 >= cycle) {
            std::cout << cycle << "\n";
            return 0;
        }
        if (l <= r) {
            v.emplace_back(l, r);
        } else {
            v.emplace_back(0, r);
            v.emplace_back(l, cycle - 1);
        }
    }
    sort(v.begin(), v.end());
    std::vector<std::pair<i64, i64>> nw;
    nw.push_back(v[0]);
    for (int i = 1; i < int(v.size()); i++) {
        if (nw[nw.size() - 1].second >= v[i].first) {
            nw[nw.size() - 1].first = std::min(nw[nw.size() - 1].first, v[i].first);
            nw[nw.size() - 1].second = std::max(nw[nw.size() - 1].second, v[i].second);
        } else {
            nw.emplace_back(v[i]);
        }
    }
    i64 ans = 0;
    for (auto [l, r] : nw) {
        ans += r - l + 1;
    }
    std::cout << ans << '\n';
}

Subtask #1
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	16 ms	1100 KB	Output is correct
3	Correct	16 ms	1192 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	292 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	288 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	288 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	292 KB	Output is correct
16	Correct	16 ms	1152 KB	Output is correct
17	Correct	155 ms	8612 KB	Output is correct
18	Incorrect	1 ms	204 KB	Output isn't correct

Subtask #2
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Incorrect	1 ms	204 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	2 ms	332 KB	Output is correct
3	Correct	2 ms	332 KB	Output is correct
4	Correct	2 ms	332 KB	Output is correct
5	Correct	1132 ms	21700 KB	Output is correct

Subtask #4
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1553 ms	60480 KB	Output is correct
3	Correct	1496 ms	60816 KB	Output is correct
4	Correct	1576 ms	60604 KB	Output is correct

Subtask #5
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1553 ms	60480 KB	Output is correct
3	Correct	1496 ms	60816 KB	Output is correct
4	Correct	1576 ms	60604 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1563 ms	60676 KB	Output is correct
7	Correct	1502 ms	42516 KB	Output is correct
8	Correct	1508 ms	42320 KB	Output is correct
9	Correct	1528 ms	42268 KB	Output is correct

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1553 ms	60480 KB	Output is correct
3	Correct	1496 ms	60816 KB	Output is correct
4	Correct	1576 ms	60604 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	151 ms	8644 KB	Output is correct
7	Correct	177 ms	8536 KB	Output is correct
8	Correct	148 ms	8564 KB	Output is correct
9	Correct	155 ms	8632 KB	Output is correct
10	Correct	151 ms	8600 KB	Output is correct
11	Correct	154 ms	8544 KB	Output is correct
12	Correct	148 ms	8544 KB	Output is correct
13	Correct	175 ms	8672 KB	Output is correct
14	Correct	152 ms	8572 KB	Output is correct
15	Correct	153 ms	8748 KB	Output is correct
16	Correct	159 ms	8728 KB	Output is correct
17	Correct	166 ms	8556 KB	Output is correct
18	Correct	1506 ms	60656 KB	Output is correct
19	Correct	1500 ms	60476 KB	Output is correct
20	Correct	1560 ms	60556 KB	Output is correct
21	Correct	153 ms	8600 KB	Output is correct
22	Correct	147 ms	8604 KB	Output is correct
23	Correct	494 ms	18528 KB	Output is correct

Subtask #7
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	155 ms	8676 KB	Output is correct
3	Correct	160 ms	8644 KB	Output is correct
4	Correct	1584 ms	60416 KB	Output is correct
5	Correct	154 ms	8624 KB	Output is correct
6	Correct	160 ms	8604 KB	Output is correct
7	Correct	181 ms	8572 KB	Output is correct
8	Correct	156 ms	8728 KB	Output is correct
9	Correct	151 ms	8532 KB	Output is correct
10	Correct	152 ms	8612 KB	Output is correct
11	Correct	154 ms	8516 KB	Output is correct
12	Correct	155 ms	8724 KB	Output is correct
13	Correct	158 ms	8624 KB	Output is correct
14	Correct	1540 ms	60540 KB	Output is correct
15	Correct	175 ms	8640 KB	Output is correct
16	Correct	1477 ms	60484 KB	Output is correct
17	Correct	1490 ms	60584 KB	Output is correct
18	Incorrect	1 ms	204 KB	Output isn't correct

Subtask #8
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	16 ms	1100 KB	Output is correct
3	Correct	16 ms	1192 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	292 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	288 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	288 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	292 KB	Output is correct
16	Correct	16 ms	1152 KB	Output is correct
17	Correct	155 ms	8612 KB	Output is correct
18	Incorrect	1 ms	204 KB	Output isn't correct

답안 #407022

Compilation message