답안 #554217

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
554217	2022-04-28T03:11:16 Z	happypotato	이상한 기계 (APIO19_strange_device)	C++17	65 / 100	1489 ms	69096 KB

strange_device

#include <bits/stdc++.h>
using namespace std;
#define int long long
int gcd(int a, int b) {
    while (b) b ^= a ^= b ^= a %= b;
    return a;
}
void solve() {
    int n, a, b;
    cin >> n >> a >> b;
    priority_queue<pair<int, bool>, vector<pair<int, bool> >, greater<pair<int, bool> > > pq;
    int mod;
    if (log2(a) + log2(b) > log2(4e18)) mod = 4e18;
    else mod = a * b / gcd(a * b, b + 1);
    while (n--) {
        int l, r;
        cin >> l >> r;
        l %= mod; r %= mod;
        if (l > r) {
            pq.push({l, true});
            pq.push({mod, false});
            pq.push({0, true});
            pq.push({r + 1, false});
        } else {
            pq.push({l, true});
            pq.push({r + 1, false});
        }
    }
    int prev = 0, ans = 0;
    int cnt = 0;
    while (!pq.empty()) {
        pair<int, bool> cur = pq.top();
        pq.pop();
        if (cnt) ans += cur.first - prev;
        prev = cur.first;
        cnt += (cur.second ? 1 : -1);
    }
    cout << ans << endl;
}
signed main() {
    solve();
}

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	15 ms	848 KB	Output is correct
3	Correct	15 ms	848 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	300 KB	Output is correct
6	Correct	0 ms	300 KB	Output is correct
7	Correct	1 ms	212 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	296 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	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	16 ms	1200 KB	Output is correct
17	Correct	147 ms	7176 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct

Subtask #2
0 / 5.0

#	결과	메모리	Grader output
1	Correct	212 KB	Output is correct
2	Incorrect	212 KB	Output isn't correct
3	Halted	0 KB	-

Subtask #3
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	2 ms	340 KB	Output is correct
3	Correct	2 ms	340 KB	Output is correct
4	Correct	2 ms	340 KB	Output is correct
5	Correct	1041 ms	33296 KB	Output is correct

Subtask #4
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1467 ms	33228 KB	Output is correct
3	Correct	1408 ms	33368 KB	Output is correct
4	Correct	1430 ms	68940 KB	Output is correct

Subtask #5
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1467 ms	33228 KB	Output is correct
3	Correct	1408 ms	33368 KB	Output is correct
4	Correct	1430 ms	68940 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1437 ms	68952 KB	Output is correct
7	Correct	1437 ms	69016 KB	Output is correct
8	Correct	1459 ms	69044 KB	Output is correct
9	Correct	1489 ms	68984 KB	Output is correct

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1467 ms	33228 KB	Output is correct
3	Correct	1408 ms	33368 KB	Output is correct
4	Correct	1430 ms	68940 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	152 ms	7328 KB	Output is correct
7	Correct	148 ms	7184 KB	Output is correct
8	Correct	142 ms	7376 KB	Output is correct
9	Correct	144 ms	7192 KB	Output is correct
10	Correct	161 ms	7244 KB	Output is correct
11	Correct	148 ms	7192 KB	Output is correct
12	Correct	151 ms	7292 KB	Output is correct
13	Correct	143 ms	7236 KB	Output is correct
14	Correct	148 ms	7200 KB	Output is correct
15	Correct	152 ms	7196 KB	Output is correct
16	Correct	149 ms	7172 KB	Output is correct
17	Correct	151 ms	7336 KB	Output is correct
18	Correct	1434 ms	68976 KB	Output is correct
19	Correct	1442 ms	68788 KB	Output is correct
20	Correct	1410 ms	69096 KB	Output is correct
21	Correct	147 ms	7244 KB	Output is correct
22	Correct	147 ms	7240 KB	Output is correct
23	Correct	476 ms	26600 KB	Output is correct

Subtask #7
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	146 ms	4932 KB	Output is correct
3	Correct	146 ms	4824 KB	Output is correct
4	Correct	1429 ms	33212 KB	Output is correct
5	Correct	144 ms	4884 KB	Output is correct
6	Correct	143 ms	4856 KB	Output is correct
7	Correct	143 ms	4820 KB	Output is correct
8	Correct	141 ms	4888 KB	Output is correct
9	Correct	193 ms	4904 KB	Output is correct
10	Correct	142 ms	4920 KB	Output is correct
11	Correct	141 ms	4852 KB	Output is correct
12	Correct	144 ms	4792 KB	Output is correct
13	Correct	144 ms	4788 KB	Output is correct
14	Correct	1411 ms	33192 KB	Output is correct
15	Correct	143 ms	4772 KB	Output is correct
16	Correct	1465 ms	69056 KB	Output is correct
17	Correct	1460 ms	68964 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct

Subtask #8
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	15 ms	848 KB	Output is correct
3	Correct	15 ms	848 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	300 KB	Output is correct
6	Correct	0 ms	300 KB	Output is correct
7	Correct	1 ms	212 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	296 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	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	16 ms	1200 KB	Output is correct
17	Correct	147 ms	7176 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Incorrect	0 ms	212 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

답안 #554217

Compilation message