Submission #519317

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
519317	2022-01-26T07:51:27 Z	tibinyte	Strange Device (APIO19_strange_device)	C++14	35 / 100	748 ms	64412 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 + 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	0 ms	204 KB	Output is correct
2	Correct	6 ms	1228 KB	Output is correct
3	Correct	7 ms	1264 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	1 ms	332 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	312 KB	Output is correct
12	Correct	1 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	0 ms	332 KB	Output is correct
16	Correct	6 ms	1264 KB	Output is correct
17	Correct	64 ms	10284 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	0 ms	204 KB	Output is correct
2	Correct	1 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	1 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	0 ms	204 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	380 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	235 ms	952 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	606 ms	63660 KB	Output is correct
3	Correct	636 ms	63476 KB	Output is correct
4	Correct	670 ms	63348 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	606 ms	63660 KB	Output is correct
3	Correct	636 ms	63476 KB	Output is correct
4	Correct	670 ms	63348 KB	Output is correct
5	Correct	1 ms	288 KB	Output is correct
6	Correct	627 ms	63440 KB	Output is correct
7	Correct	644 ms	63444 KB	Output is correct
8	Correct	626 ms	63372 KB	Output is correct
9	Correct	748 ms	63404 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	606 ms	63660 KB	Output is correct
3	Correct	636 ms	63476 KB	Output is correct
4	Correct	670 ms	63348 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	55 ms	9952 KB	Output is correct
7	Correct	58 ms	10080 KB	Output is correct
8	Correct	58 ms	10052 KB	Output is correct
9	Correct	65 ms	10048 KB	Output is correct
10	Correct	55 ms	10048 KB	Output is correct
11	Correct	55 ms	9980 KB	Output is correct
12	Correct	56 ms	10020 KB	Output is correct
13	Correct	66 ms	10076 KB	Output is correct
14	Correct	55 ms	9984 KB	Output is correct
15	Correct	66 ms	9960 KB	Output is correct
16	Correct	67 ms	10004 KB	Output is correct
17	Correct	63 ms	10048 KB	Output is correct
18	Correct	629 ms	63536 KB	Output is correct
19	Correct	677 ms	63300 KB	Output is correct
20	Correct	692 ms	63500 KB	Output is correct
21	Correct	59 ms	10068 KB	Output is correct
22	Correct	58 ms	10032 KB	Output is correct
23	Correct	109 ms	3792 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	69 ms	10012 KB	Output is correct
3	Correct	63 ms	10044 KB	Output is correct
4	Correct	697 ms	64412 KB	Output is correct
5	Correct	61 ms	10084 KB	Output is correct
6	Correct	66 ms	10052 KB	Output is correct
7	Correct	73 ms	10024 KB	Output is correct
8	Correct	66 ms	10056 KB	Output is correct
9	Correct	65 ms	10124 KB	Output is correct
10	Correct	56 ms	10028 KB	Output is correct
11	Correct	65 ms	10168 KB	Output is correct
12	Correct	59 ms	10156 KB	Output is correct
13	Correct	65 ms	10176 KB	Output is correct
14	Correct	687 ms	63720 KB	Output is correct
15	Correct	61 ms	10252 KB	Output is correct
16	Correct	633 ms	63592 KB	Output is correct
17	Correct	625 ms	63712 KB	Output is correct
18	Incorrect	1 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	1228 KB	Output is correct
3	Correct	7 ms	1264 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	1 ms	332 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	312 KB	Output is correct
12	Correct	1 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	0 ms	332 KB	Output is correct
16	Correct	6 ms	1264 KB	Output is correct
17	Correct	64 ms	10284 KB	Output is correct
18	Incorrect	0 ms	204 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Submission #519317

Compilation message