Submission #519324

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
519324	2022-01-26T07:57:06 Z	tibinyte	Strange Device (APIO19_strange_device)	C++14	35 / 100	754 ms	63080 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 = 1e18;
	}
	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]--;
	};
	wh[p - 1] = 0;
	wh[0] = 0;
	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	0 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	0 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	1 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	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	6 ms	840 KB	Output is correct
17	Correct	58 ms	6580 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	Memory	Grader output
1	Correct	204 KB	Output is correct
2	Correct	204 KB	Output is correct
3	Correct	204 KB	Output is correct
4	Correct	204 KB	Output is correct
5	Incorrect	204 KB	Output isn't correct
6	Halted	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	2 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	231 ms	288 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Output is correct
2	Correct	650 ms	63076 KB	Output is correct
3	Correct	672 ms	63072 KB	Output is correct
4	Correct	723 ms	62916 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Output is correct
2	Correct	650 ms	63076 KB	Output is correct
3	Correct	672 ms	63072 KB	Output is correct
4	Correct	723 ms	62916 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	657 ms	62904 KB	Output is correct
7	Correct	669 ms	62876 KB	Output is correct
8	Correct	668 ms	62812 KB	Output is correct
9	Correct	754 ms	62896 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Output is correct
2	Correct	650 ms	63076 KB	Output is correct
3	Correct	672 ms	63072 KB	Output is correct
4	Correct	723 ms	62916 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	54 ms	6636 KB	Output is correct
7	Correct	70 ms	6524 KB	Output is correct
8	Correct	65 ms	6480 KB	Output is correct
9	Correct	72 ms	6532 KB	Output is correct
10	Correct	57 ms	6476 KB	Output is correct
11	Correct	55 ms	6536 KB	Output is correct
12	Correct	64 ms	6468 KB	Output is correct
13	Correct	69 ms	6476 KB	Output is correct
14	Correct	57 ms	6564 KB	Output is correct
15	Correct	68 ms	6604 KB	Output is correct
16	Correct	65 ms	6496 KB	Output is correct
17	Correct	65 ms	6448 KB	Output is correct
18	Correct	637 ms	62828 KB	Output is correct
19	Correct	677 ms	62904 KB	Output is correct
20	Correct	708 ms	62848 KB	Output is correct
21	Correct	60 ms	6528 KB	Output is correct
22	Correct	64 ms	6536 KB	Output is correct
23	Correct	103 ms	204 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	60 ms	6512 KB	Output is correct
3	Correct	62 ms	6540 KB	Output is correct
4	Correct	734 ms	62940 KB	Output is correct
5	Correct	64 ms	6568 KB	Output is correct
6	Correct	65 ms	6484 KB	Output is correct
7	Correct	66 ms	6516 KB	Output is correct
8	Correct	65 ms	6576 KB	Output is correct
9	Correct	63 ms	6548 KB	Output is correct
10	Correct	69 ms	6548 KB	Output is correct
11	Correct	71 ms	6468 KB	Output is correct
12	Correct	59 ms	6472 KB	Output is correct
13	Correct	66 ms	6508 KB	Output is correct
14	Correct	751 ms	62920 KB	Output is correct
15	Correct	53 ms	6524 KB	Output is correct
16	Correct	603 ms	62872 KB	Output is correct
17	Correct	627 ms	63080 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	0 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	0 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	1 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	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	6 ms	840 KB	Output is correct
17	Correct	58 ms	6580 KB	Output is correct
18	Incorrect	0 ms	204 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Submission #519324

Compilation message