Submission #519319

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
519319	2022-01-26T07:53:59 Z	tibinyte	Strange Device (APIO19_strange_device)	C++14	35 / 100	786 ms	63020 KB

strange_device

#include <bits/stdc++.h>
using namespace std;
bool will_overflow(long long a, long long b) {
	long long c = a * b;
	if (a != c / b) {
		return true;
	}
	return false;
}
long long gcd(long long a, long long b) {
	while (b) {
		long long c = a % b;
		a = b;
		b = c;
	}
	return a;
}
int main() {
	cin.tie(nullptr)->ios_base::sync_with_stdio(false);
	long long n, a, b;
	cin >> n >> a >> b;
	long long p = 0;
	if (will_overflow(a / gcd(a, b + 1), b)) {
		p = 4e18 + 1;
	}
	else {
		p = a / gcd(a, b + 1) * b;
	}
	map<long long, long long> wh;
	auto update = [&](long long st, long long dr) {
		wh[st]++;
		wh[dr + 1]--;
	};
	for (long long i = 1; i <= n; ++i) {
		long long st, dr;
		cin >> st >> dr;
		long long lg = (dr - st) + 1;
		st %= p;
		if (st + lg - 1 < p) {
			update(st, st + lg - 1);
		}
		else {
			update(st, p - 1);
			lg -= (p - st);
			st = 0;
			if (st + lg - 1 < p) {
				update(st, st + lg - 1);
			}
			else {
				cout << p << '\n';
				return 0;
			}
		}
	}
	long long ans = 0;
	long long s = 0;
	for (map<long long, long long>::iterator i = wh.begin(); i != prev(wh.end()); ++i) {
		s += i->second;
		long long st = i->first, dr = next(i)->first - 1;
		if (s) {
			ans += dr - st + 1;
		}
	}
	cout << ans;
}

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	6 ms	844 KB	Output is correct
3	Correct	6 ms	844 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	204 KB	Output is correct
7	Correct	0 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	0 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	0 ms	204 KB	Output is correct
13	Correct	0 ms	204 KB	Output is correct
14	Correct	0 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	7 ms	840 KB	Output is correct
17	Correct	79 ms	6540 KB	Output is correct
18	Incorrect	0 ms	204 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #2
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Incorrect	0 ms	204 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	236 ms	204 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	667 ms	62840 KB	Output is correct
3	Correct	647 ms	62920 KB	Output is correct
4	Correct	708 ms	62916 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	667 ms	62840 KB	Output is correct
3	Correct	647 ms	62920 KB	Output is correct
4	Correct	708 ms	62916 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	635 ms	62820 KB	Output is correct
7	Correct	714 ms	62968 KB	Output is correct
8	Correct	662 ms	62956 KB	Output is correct
9	Correct	723 ms	62884 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	667 ms	62840 KB	Output is correct
3	Correct	647 ms	62920 KB	Output is correct
4	Correct	708 ms	62916 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	52 ms	6556 KB	Output is correct
7	Correct	56 ms	6472 KB	Output is correct
8	Correct	55 ms	6564 KB	Output is correct
9	Correct	60 ms	6464 KB	Output is correct
10	Correct	61 ms	6544 KB	Output is correct
11	Correct	55 ms	6596 KB	Output is correct
12	Correct	52 ms	6468 KB	Output is correct
13	Correct	59 ms	6540 KB	Output is correct
14	Correct	57 ms	6676 KB	Output is correct
15	Correct	64 ms	6516 KB	Output is correct
16	Correct	62 ms	6468 KB	Output is correct
17	Correct	63 ms	6508 KB	Output is correct
18	Correct	618 ms	63020 KB	Output is correct
19	Correct	786 ms	62864 KB	Output is correct
20	Correct	720 ms	62968 KB	Output is correct
21	Correct	55 ms	6500 KB	Output is correct
22	Correct	82 ms	6452 KB	Output is correct
23	Correct	113 ms	292 KB	Output is correct

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	61 ms	6576 KB	Output is correct
3	Correct	61 ms	6560 KB	Output is correct
4	Correct	747 ms	62948 KB	Output is correct
5	Correct	65 ms	6596 KB	Output is correct
6	Correct	63 ms	6468 KB	Output is correct
7	Correct	63 ms	6572 KB	Output is correct
8	Correct	66 ms	6552 KB	Output is correct
9	Correct	60 ms	6472 KB	Output is correct
10	Correct	58 ms	6516 KB	Output is correct
11	Correct	62 ms	6448 KB	Output is correct
12	Correct	55 ms	6468 KB	Output is correct
13	Correct	68 ms	6596 KB	Output is correct
14	Correct	688 ms	62904 KB	Output is correct
15	Correct	80 ms	6536 KB	Output is correct
16	Correct	619 ms	62932 KB	Output is correct
17	Correct	611 ms	62940 KB	Output is correct
18	Incorrect	0 ms	204 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	6 ms	844 KB	Output is correct
3	Correct	6 ms	844 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	204 KB	Output is correct
7	Correct	0 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	0 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	0 ms	204 KB	Output is correct
13	Correct	0 ms	204 KB	Output is correct
14	Correct	0 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	7 ms	840 KB	Output is correct
17	Correct	79 ms	6540 KB	Output is correct
18	Incorrect	0 ms	204 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Submission #519319

Compilation message