답안 #654686

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
654686	2022-11-01T08:59:35 Z	horiseun	이상한 기계 (APIO19_strange_device)	C++11	35 / 100	644 ms	87908 KB

strange_device

#include <iostream>
#include <vector>
#include <set>
#include <tuple>
#include <algorithm>
using namespace std;

#define ll long long
#define f first
#define s second

ll a, b, n, l, r, p, ans, c, lft;
vector<pair<ll, bool>> v;

ll gcd(ll x, ll y) {
    if (y == 0) return x;
    return gcd(y, x % y);
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> a >> b;
    p = b * (a / gcd(a, b + 1));
    for (int i = 0; i < n; i++) {
        cin >> l >> r;
        if (r - l >= p) {
            cout << p << "\n";
            return 0;
        }
        if ((l + p - 1) % p > (r + p - 1) % p) {
            v.push_back({1, 0});
            v.push_back({(l + p - 1) % p + 1, 0});
            v.push_back({(r + p - 1) % p + 1, 1});
            v.push_back({p, 1});
        } else {
            v.push_back({(l + p - 1) % p + 1, 0});
            v.push_back({(r + p - 1) % p + 1, 1});
        }
    }
    sort(v.begin(), v.end());

    lft = -1;
    for (pair<ll, bool> i : v) {
        if (!i.s) {
            c++;
            if (lft == -1) lft = i.f;
        } else {
            c--;
            if (c == 0) {
                ans += (i.f - lft + 1);
                lft = -1;
            }
        }
    }
    cout << ans << "\n";

}

Subtask #1
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	6 ms	1372 KB	Output is correct
3	Correct	6 ms	1300 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	316 KB	Output is correct
7	Correct	1 ms	316 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	324 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	0 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	7 ms	1240 KB	Output is correct
17	Correct	71 ms	7356 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

#	결과	실행 시간	메모리	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	0 ms	212 KB	Output is correct
5	Incorrect	1 ms	320 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #3
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	316 KB	Output is correct
2	Correct	2 ms	340 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	544 ms	87908 KB	Output is correct

Subtask #4
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	320 KB	Output is correct
2	Correct	536 ms	35504 KB	Output is correct
3	Correct	643 ms	68956 KB	Output is correct
4	Correct	544 ms	69036 KB	Output is correct

Subtask #5
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	320 KB	Output is correct
2	Correct	536 ms	35504 KB	Output is correct
3	Correct	643 ms	68956 KB	Output is correct
4	Correct	544 ms	69036 KB	Output is correct
5	Correct	1 ms	320 KB	Output is correct
6	Correct	573 ms	68912 KB	Output is correct
7	Correct	556 ms	68888 KB	Output is correct
8	Correct	580 ms	68844 KB	Output is correct
9	Correct	644 ms	68968 KB	Output is correct

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	320 KB	Output is correct
2	Correct	536 ms	35504 KB	Output is correct
3	Correct	643 ms	68956 KB	Output is correct
4	Correct	544 ms	69036 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	52 ms	7300 KB	Output is correct
7	Correct	50 ms	7236 KB	Output is correct
8	Correct	47 ms	7260 KB	Output is correct
9	Correct	51 ms	7224 KB	Output is correct
10	Correct	49 ms	7228 KB	Output is correct
11	Correct	49 ms	7212 KB	Output is correct
12	Correct	46 ms	7236 KB	Output is correct
13	Correct	57 ms	7220 KB	Output is correct
14	Correct	47 ms	7240 KB	Output is correct
15	Correct	56 ms	7212 KB	Output is correct
16	Correct	54 ms	7284 KB	Output is correct
17	Correct	49 ms	7232 KB	Output is correct
18	Correct	507 ms	68956 KB	Output is correct
19	Correct	476 ms	69044 KB	Output is correct
20	Correct	593 ms	69060 KB	Output is correct
21	Correct	55 ms	7220 KB	Output is correct
22	Correct	44 ms	7216 KB	Output is correct
23	Correct	184 ms	43024 KB	Output is correct

Subtask #7
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	316 KB	Output is correct
2	Correct	53 ms	7236 KB	Output is correct
3	Correct	57 ms	7236 KB	Output is correct
4	Correct	621 ms	69192 KB	Output is correct
5	Correct	54 ms	7260 KB	Output is correct
6	Correct	52 ms	7300 KB	Output is correct
7	Correct	53 ms	7248 KB	Output is correct
8	Correct	54 ms	7240 KB	Output is correct
9	Correct	52 ms	7296 KB	Output is correct
10	Correct	56 ms	7312 KB	Output is correct
11	Correct	59 ms	7244 KB	Output is correct
12	Correct	60 ms	7384 KB	Output is correct
13	Correct	54 ms	7372 KB	Output is correct
14	Correct	608 ms	68876 KB	Output is correct
15	Correct	55 ms	7220 KB	Output is correct
16	Correct	509 ms	68520 KB	Output is correct
17	Correct	506 ms	68908 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

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	6 ms	1372 KB	Output is correct
3	Correct	6 ms	1300 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	316 KB	Output is correct
7	Correct	1 ms	316 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	324 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	0 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	7 ms	1240 KB	Output is correct
17	Correct	71 ms	7356 KB	Output is correct
18	Incorrect	1 ms	212 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

답안 #654686

Compilation message