답안 #1059826

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1059826	2024-08-15T08:32:37 Z	dpsaveslives	이상한 기계 (APIO19_strange_device)	C++17	35 / 100	1198 ms	45676 KB

strange_device

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 4e6;
int n, m, tot, sum[maxn + 3];
ll A, B, C, l, r, temp[maxn + 3];
pair<ll, ll> sect[maxn + 3];
ll gcd(ll a, ll b) {
	return b ? gcd(b, a % b) : a;
}
int main() {
	cin >> n >> A >> B;
	C = A / gcd(A, B + 1) * B; //AB/gcd(A,B+1)
	for (int i = 1; i <= n; i++) {
		cin >> l >> r;
		if (r - l + 1 >= C) {
			cout << C << "\n";
			return 0;
		}
		l %= C, r %= C; //"how far they are into" the cycle they are in (I feel so stupid for not seeing that all you need to do is %)
		if (l <= r) {
			sect[++tot] = make_pair(l, r);
		} else {
			sect[++tot] = make_pair(0, r);
			sect[++tot] = make_pair(l, C - 1);
		}
	}
	for (int i = 1; i <= tot; i++) {
		temp[++m] = sect[i].first;
		temp[++m] = sect[i].second + 1;
	}
	sort(temp + 1, temp + m + 1);
	for (int i = 1; i <= tot; i++) {
		int x = lower_bound(temp + 1, temp + m + 1, sect[i].first) - temp; //find the one that ends first that starts with sect[i].first
		int y = lower_bound(temp + 1, temp + m + 1, sect[i].second + 1) - temp; //find the first one that is >= sect[i].second+1
		sum[x]++, sum[y]--;
	}
	ll ans = 0;
	for (int i = 1; i <= m; i++) {
		sum[i] += sum[i - 1];
		if (sum[i]) {
			ans += temp[i + 1] - temp[i];
		}
	}
	printf("%lld\n", ans);
	return 0;
}

Subtask #1
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2392 KB	Output is correct
2	Correct	10 ms	4696 KB	Output is correct
3	Correct	16 ms	4700 KB	Output is correct
4	Correct	1 ms	4444 KB	Output is correct
5	Correct	0 ms	4444 KB	Output is correct
6	Correct	1 ms	4444 KB	Output is correct
7	Correct	1 ms	4444 KB	Output is correct
8	Correct	1 ms	4444 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	4444 KB	Output is correct
11	Correct	1 ms	4444 KB	Output is correct
12	Correct	1 ms	4440 KB	Output is correct
13	Correct	0 ms	4444 KB	Output is correct
14	Correct	1 ms	4444 KB	Output is correct
15	Correct	1 ms	4444 KB	Output is correct
16	Correct	10 ms	4688 KB	Output is correct
17	Correct	111 ms	10836 KB	Output is correct
18	Incorrect	1 ms	2648 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #2
0 / 5.0

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

Subtask #3
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2396 KB	Output is correct
2	Correct	2 ms	4440 KB	Output is correct
3	Correct	2 ms	4440 KB	Output is correct
4	Correct	2 ms	4444 KB	Output is correct
5	Correct	633 ms	44648 KB	Output is correct

Subtask #4
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2392 KB	Output is correct
2	Correct	979 ms	44632 KB	Output is correct
3	Correct	997 ms	45672 KB	Output is correct
4	Correct	977 ms	44632 KB	Output is correct

Subtask #5
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2392 KB	Output is correct
2	Correct	979 ms	44632 KB	Output is correct
3	Correct	997 ms	45672 KB	Output is correct
4	Correct	977 ms	44632 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	1000 ms	44640 KB	Output is correct
7	Correct	958 ms	44640 KB	Output is correct
8	Correct	1016 ms	44632 KB	Output is correct
9	Correct	1049 ms	45648 KB	Output is correct

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2392 KB	Output is correct
2	Correct	979 ms	44632 KB	Output is correct
3	Correct	997 ms	45672 KB	Output is correct
4	Correct	977 ms	44632 KB	Output is correct
5	Correct	1 ms	2392 KB	Output is correct
6	Correct	95 ms	10812 KB	Output is correct
7	Correct	98 ms	10824 KB	Output is correct
8	Correct	98 ms	10836 KB	Output is correct
9	Correct	96 ms	10832 KB	Output is correct
10	Correct	93 ms	10836 KB	Output is correct
11	Correct	98 ms	10860 KB	Output is correct
12	Correct	96 ms	10832 KB	Output is correct
13	Correct	101 ms	10840 KB	Output is correct
14	Correct	97 ms	10716 KB	Output is correct
15	Correct	104 ms	10836 KB	Output is correct
16	Correct	105 ms	10836 KB	Output is correct
17	Correct	96 ms	10856 KB	Output is correct
18	Correct	1014 ms	42836 KB	Output is correct
19	Correct	1059 ms	42604 KB	Output is correct
20	Correct	1112 ms	42592 KB	Output is correct
21	Correct	121 ms	10836 KB	Output is correct
22	Correct	93 ms	10832 KB	Output is correct
23	Correct	290 ms	19024 KB	Output is correct

Subtask #7
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2396 KB	Output is correct
2	Correct	114 ms	10856 KB	Output is correct
3	Correct	106 ms	10836 KB	Output is correct
4	Correct	1117 ms	45656 KB	Output is correct
5	Correct	104 ms	10856 KB	Output is correct
6	Correct	116 ms	10844 KB	Output is correct
7	Correct	101 ms	10836 KB	Output is correct
8	Correct	103 ms	10832 KB	Output is correct
9	Correct	107 ms	10836 KB	Output is correct
10	Correct	145 ms	10724 KB	Output is correct
11	Correct	102 ms	10832 KB	Output is correct
12	Correct	110 ms	10840 KB	Output is correct
13	Correct	108 ms	10836 KB	Output is correct
14	Correct	1105 ms	45668 KB	Output is correct
15	Correct	113 ms	10836 KB	Output is correct
16	Correct	1107 ms	44648 KB	Output is correct
17	Correct	1198 ms	45676 KB	Output is correct
18	Incorrect	1 ms	2396 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #8
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2392 KB	Output is correct
2	Correct	10 ms	4696 KB	Output is correct
3	Correct	16 ms	4700 KB	Output is correct
4	Correct	1 ms	4444 KB	Output is correct
5	Correct	0 ms	4444 KB	Output is correct
6	Correct	1 ms	4444 KB	Output is correct
7	Correct	1 ms	4444 KB	Output is correct
8	Correct	1 ms	4444 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	4444 KB	Output is correct
11	Correct	1 ms	4444 KB	Output is correct
12	Correct	1 ms	4440 KB	Output is correct
13	Correct	0 ms	4444 KB	Output is correct
14	Correct	1 ms	4444 KB	Output is correct
15	Correct	1 ms	4444 KB	Output is correct
16	Correct	10 ms	4688 KB	Output is correct
17	Correct	111 ms	10836 KB	Output is correct
18	Incorrect	1 ms	2648 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

답안 #1059826

Compilation message