Submission #959309

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
959309	2024-04-07T23:28:42 Z	NK_	Strange Device (APIO19_strange_device)	C++17	100 / 100	610 ms	69152 KB

strange_device

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())

using ll = long long;
template<class T> using V = vector<T>;
using vl = V<ll>;

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int N; ll A, B; cin >> N >> A >> B;

	ll K = A / __gcd(B + 1, A);

	if (K > ll(1e18) / B) K = -1;
	else K *= B;

	V<array<ll, 2>> E;
	auto add = [&](ll l, ll r) {
		E.pb(array<ll, 2>{l, +1});
		E.pb(array<ll, 2>{r + 1, -1});
	};

	ll ans = 0;
	for(int i = 0; i < N; i++) {
		ll l, r; cin >> l >> r;
		ll len = r - l + 1;

		if (K == -1) ans += len;

		if (len >= K) add(0, K - 1);
		else {
			l %= K, r %= K;
			if (l <= r) add(l, r);
			else add(l, K - 1), add(0, r);
		}

	}

	if (K == -1) {
		cout << ans << nl;
		exit(0-0);
	}

	int have = 0; 
	sort(begin(E), end(E));

	for(int i = 0; i < sz(E); i++) {
		int j = i; while(j < sz(E) && E[j][0] == E[i][0]) {
			have += E[j][1]; j++;
		}

		if (have && j < sz(E)) {
			ll amt = E[j][0] - E[i][0];
			// cout << E[j][0] << " " << E[i][0] << endl;
			ans += amt;
		}

		i = j - 1;
	}

	cout << ans << nl;
	
	exit(0-0);
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	5 ms	1248 KB	Output is correct
3	Correct	7 ms	1248 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	600 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	344 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	344 KB	Output is correct
16	Correct	5 ms	1248 KB	Output is correct
17	Correct	52 ms	7924 KB	Output is correct
18	Correct	0 ms	344 KB	Output is correct

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	456 KB	Output is correct

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	464 KB	Output is correct
3	Correct	1 ms	532 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	363 ms	56300 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	492 ms	67304 KB	Output is correct
3	Correct	508 ms	67440 KB	Output is correct
4	Correct	464 ms	67316 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	492 ms	67304 KB	Output is correct
3	Correct	508 ms	67440 KB	Output is correct
4	Correct	464 ms	67316 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	499 ms	67476 KB	Output is correct
7	Correct	518 ms	67700 KB	Output is correct
8	Correct	466 ms	67212 KB	Output is correct
9	Correct	571 ms	67168 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	492 ms	67304 KB	Output is correct
3	Correct	508 ms	67440 KB	Output is correct
4	Correct	464 ms	67316 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	41 ms	8324 KB	Output is correct
7	Correct	45 ms	8816 KB	Output is correct
8	Correct	45 ms	7304 KB	Output is correct
9	Correct	43 ms	7932 KB	Output is correct
10	Correct	40 ms	9032 KB	Output is correct
11	Correct	45 ms	8916 KB	Output is correct
12	Correct	61 ms	7624 KB	Output is correct
13	Correct	49 ms	9160 KB	Output is correct
14	Correct	42 ms	9160 KB	Output is correct
15	Correct	52 ms	7628 KB	Output is correct
16	Correct	53 ms	7628 KB	Output is correct
17	Correct	43 ms	7480 KB	Output is correct
18	Correct	488 ms	67476 KB	Output is correct
19	Correct	442 ms	67480 KB	Output is correct
20	Correct	577 ms	67512 KB	Output is correct
21	Correct	55 ms	8192 KB	Output is correct
22	Correct	38 ms	7636 KB	Output is correct
23	Correct	126 ms	28416 KB	Output is correct

Subtask #7
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	53 ms	8404 KB	Output is correct
3	Correct	49 ms	7736 KB	Output is correct
4	Correct	587 ms	68248 KB	Output is correct
5	Correct	49 ms	9160 KB	Output is correct
6	Correct	50 ms	9016 KB	Output is correct
7	Correct	50 ms	7780 KB	Output is correct
8	Correct	55 ms	8740 KB	Output is correct
9	Correct	48 ms	9160 KB	Output is correct
10	Correct	65 ms	8992 KB	Output is correct
11	Correct	49 ms	8652 KB	Output is correct
12	Correct	43 ms	7636 KB	Output is correct
13	Correct	52 ms	8136 KB	Output is correct
14	Correct	572 ms	68700 KB	Output is correct
15	Correct	54 ms	8288 KB	Output is correct
16	Correct	433 ms	67484 KB	Output is correct
17	Correct	466 ms	67776 KB	Output is correct
18	Correct	1 ms	348 KB	Output is correct

Subtask #8
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	5 ms	1248 KB	Output is correct
3	Correct	7 ms	1248 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	600 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	344 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	344 KB	Output is correct
16	Correct	5 ms	1248 KB	Output is correct
17	Correct	52 ms	7924 KB	Output is correct
18	Correct	0 ms	344 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct
23	Correct	0 ms	456 KB	Output is correct
24	Correct	0 ms	344 KB	Output is correct
25	Correct	1 ms	464 KB	Output is correct
26	Correct	1 ms	532 KB	Output is correct
27	Correct	1 ms	348 KB	Output is correct
28	Correct	363 ms	56300 KB	Output is correct
29	Correct	1 ms	348 KB	Output is correct
30	Correct	492 ms	67304 KB	Output is correct
31	Correct	508 ms	67440 KB	Output is correct
32	Correct	464 ms	67316 KB	Output is correct
33	Correct	0 ms	348 KB	Output is correct
34	Correct	499 ms	67476 KB	Output is correct
35	Correct	518 ms	67700 KB	Output is correct
36	Correct	466 ms	67212 KB	Output is correct
37	Correct	571 ms	67168 KB	Output is correct
38	Correct	1 ms	344 KB	Output is correct
39	Correct	41 ms	8324 KB	Output is correct
40	Correct	45 ms	8816 KB	Output is correct
41	Correct	45 ms	7304 KB	Output is correct
42	Correct	43 ms	7932 KB	Output is correct
43	Correct	40 ms	9032 KB	Output is correct
44	Correct	45 ms	8916 KB	Output is correct
45	Correct	61 ms	7624 KB	Output is correct
46	Correct	49 ms	9160 KB	Output is correct
47	Correct	42 ms	9160 KB	Output is correct
48	Correct	52 ms	7628 KB	Output is correct
49	Correct	53 ms	7628 KB	Output is correct
50	Correct	43 ms	7480 KB	Output is correct
51	Correct	488 ms	67476 KB	Output is correct
52	Correct	442 ms	67480 KB	Output is correct
53	Correct	577 ms	67512 KB	Output is correct
54	Correct	55 ms	8192 KB	Output is correct
55	Correct	38 ms	7636 KB	Output is correct
56	Correct	126 ms	28416 KB	Output is correct
57	Correct	0 ms	344 KB	Output is correct
58	Correct	53 ms	8404 KB	Output is correct
59	Correct	49 ms	7736 KB	Output is correct
60	Correct	587 ms	68248 KB	Output is correct
61	Correct	49 ms	9160 KB	Output is correct
62	Correct	50 ms	9016 KB	Output is correct
63	Correct	50 ms	7780 KB	Output is correct
64	Correct	55 ms	8740 KB	Output is correct
65	Correct	48 ms	9160 KB	Output is correct
66	Correct	65 ms	8992 KB	Output is correct
67	Correct	49 ms	8652 KB	Output is correct
68	Correct	43 ms	7636 KB	Output is correct
69	Correct	52 ms	8136 KB	Output is correct
70	Correct	572 ms	68700 KB	Output is correct
71	Correct	54 ms	8288 KB	Output is correct
72	Correct	433 ms	67484 KB	Output is correct
73	Correct	466 ms	67776 KB	Output is correct
74	Correct	1 ms	348 KB	Output is correct
75	Correct	0 ms	348 KB	Output is correct
76	Correct	1 ms	344 KB	Output is correct
77	Correct	1 ms	348 KB	Output is correct
78	Correct	0 ms	348 KB	Output is correct
79	Correct	4 ms	1248 KB	Output is correct
80	Correct	595 ms	68552 KB	Output is correct
81	Correct	610 ms	68960 KB	Output is correct
82	Correct	549 ms	69000 KB	Output is correct
83	Correct	530 ms	68768 KB	Output is correct
84	Correct	533 ms	68852 KB	Output is correct
85	Correct	561 ms	69152 KB	Output is correct
86	Correct	120 ms	28492 KB	Output is correct
87	Correct	1 ms	344 KB	Output is correct

Submission #959309

Compilation message