답안 #145367

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
145367	2019-08-19T17:35:43 Z	dolphingarlic	이상한 기계 (APIO19_strange_device)	C++14	35 / 100	1016 ms	68212 KB

strange_device

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define FOR(i, x, y) for (ll i = x; i < y; i++)
typedef long long ll;
using namespace std;

// Observation: pairs are periodic, period = B * (A / gcd(A, B + 1))
// We can thus "line sweep" i.e. keep a vector of events and +1 for add,
// -1 for remove and count as long as positive

ll gcd(ll a, ll b) { return (b == 0 ? a : gcd(b, a % b)); }

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n, a, b;
    cin >> n >> a >> b;
    ll period = b * (a / gcd(a, b + 1));
    vector<pair<ll, int>> events;
    FOR(i, 0, n) {
        ll x, y;
        cin >> x >> y;
        x += period - 1;
        y += period - 1;
        if (y - x >= period) {
            return cout << period << '\n', 0;
        }
        if (x % period > y % period) {
            events.push_back(make_pair(1, 0));
            events.push_back(make_pair(y % period + 1, 1));
            events.push_back(make_pair(x % period + 1, 0));
            events.push_back(make_pair(period, 1));
        } else {
            events.push_back(make_pair(x % period + 1, 0));
            events.push_back(make_pair(y % period + 1, 1));
        }
    }
    sort(events.begin(), events.end());
    ll cnt = 0, leftmost = -1, ans = 0;
    for (auto& i : events) {
        if (!i.second) {
            cnt++;
            if (leftmost == -1) leftmost = i.first;
        } else {
            cnt--;
            if (cnt == 0) {
                ans += (i.first - leftmost + 1);
                leftmost = -1;
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

Subtask #1
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	380 KB	Output is correct
2	Correct	10 ms	1396 KB	Output is correct
3	Correct	10 ms	1332 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	380 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	10 ms	1272 KB	Output is correct
17	Correct	88 ms	6220 KB	Output is correct
18	Incorrect	2 ms	376 KB	Output isn't correct

Subtask #2
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	380 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Incorrect	2 ms	376 KB	Output isn't correct

Subtask #3
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	504 KB	Output is correct
3	Correct	3 ms	504 KB	Output is correct
4	Correct	3 ms	376 KB	Output is correct
5	Correct	696 ms	68212 KB	Output is correct

Subtask #4
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	757 ms	35628 KB	Output is correct
3	Correct	802 ms	34476 KB	Output is correct
4	Correct	774 ms	34376 KB	Output is correct

Subtask #5
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	757 ms	35628 KB	Output is correct
3	Correct	802 ms	34476 KB	Output is correct
4	Correct	774 ms	34376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	780 ms	34532 KB	Output is correct
7	Correct	767 ms	34356 KB	Output is correct
8	Correct	758 ms	34540 KB	Output is correct
9	Correct	859 ms	34476 KB	Output is correct

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	757 ms	35628 KB	Output is correct
3	Correct	802 ms	34476 KB	Output is correct
4	Correct	774 ms	34376 KB	Output is correct
5	Correct	2 ms	380 KB	Output is correct
6	Correct	75 ms	6252 KB	Output is correct
7	Correct	79 ms	6336 KB	Output is correct
8	Correct	77 ms	6256 KB	Output is correct
9	Correct	78 ms	6248 KB	Output is correct
10	Correct	73 ms	6252 KB	Output is correct
11	Correct	78 ms	6248 KB	Output is correct
12	Correct	74 ms	6368 KB	Output is correct
13	Correct	85 ms	6400 KB	Output is correct
14	Correct	75 ms	6248 KB	Output is correct
15	Correct	87 ms	6284 KB	Output is correct
16	Correct	85 ms	6292 KB	Output is correct
17	Correct	78 ms	6248 KB	Output is correct
18	Correct	783 ms	34896 KB	Output is correct
19	Correct	736 ms	34972 KB	Output is correct
20	Correct	884 ms	35124 KB	Output is correct
21	Correct	87 ms	6568 KB	Output is correct
22	Correct	89 ms	6220 KB	Output is correct
23	Correct	282 ms	35904 KB	Output is correct

Subtask #7
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	84 ms	6248 KB	Output is correct
3	Correct	87 ms	5996 KB	Output is correct
4	Correct	1016 ms	34604 KB	Output is correct
5	Correct	84 ms	5964 KB	Output is correct
6	Correct	84 ms	6088 KB	Output is correct
7	Correct	84 ms	6016 KB	Output is correct
8	Correct	85 ms	6272 KB	Output is correct
9	Correct	81 ms	6240 KB	Output is correct
10	Correct	124 ms	6240 KB	Output is correct
11	Correct	84 ms	6368 KB	Output is correct
12	Correct	77 ms	6268 KB	Output is correct
13	Correct	86 ms	6248 KB	Output is correct
14	Correct	854 ms	34888 KB	Output is correct
15	Correct	86 ms	6496 KB	Output is correct
16	Correct	723 ms	35492 KB	Output is correct
17	Correct	763 ms	35376 KB	Output is correct
18	Incorrect	2 ms	376 KB	Output isn't correct

Subtask #8
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	380 KB	Output is correct
2	Correct	10 ms	1396 KB	Output is correct
3	Correct	10 ms	1332 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	380 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	10 ms	1272 KB	Output is correct
17	Correct	88 ms	6220 KB	Output is correct
18	Incorrect	2 ms	376 KB	Output isn't correct

답안 #145367

Compilation message