Submission #959306

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
959306	2024-04-07T23:21:57 Z	NK_	Strange Device (APIO19_strange_device)	C++17	35 / 100	580 ms	70536 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 C = 1LL + (B % A);

	ll K = A / gcd(C, A) * B;

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

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

		ll len = r - l + 1;
		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);
		}

	}

	int have = 0; ll ans = 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) {
			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
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	5 ms	1244 KB	Output is correct
3	Correct	5 ms	1248 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	344 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	1 ms	344 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	6 ms	1248 KB	Output is correct
17	Correct	50 ms	7892 KB	Output is correct
18	Incorrect	1 ms	348 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #2
0 / 5.0

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

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	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	304 ms	58280 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	438 ms	69512 KB	Output is correct
3	Correct	460 ms	69292 KB	Output is correct
4	Correct	438 ms	70536 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	438 ms	69512 KB	Output is correct
3	Correct	460 ms	69292 KB	Output is correct
4	Correct	438 ms	70536 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	450 ms	69004 KB	Output is correct
7	Correct	452 ms	69920 KB	Output is correct
8	Correct	464 ms	69288 KB	Output is correct
9	Correct	504 ms	69972 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	438 ms	69512 KB	Output is correct
3	Correct	460 ms	69292 KB	Output is correct
4	Correct	438 ms	70536 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	44 ms	8404 KB	Output is correct
7	Correct	44 ms	7368 KB	Output is correct
8	Correct	41 ms	7636 KB	Output is correct
9	Correct	50 ms	7628 KB	Output is correct
10	Correct	45 ms	8476 KB	Output is correct
11	Correct	50 ms	8908 KB	Output is correct
12	Correct	40 ms	7888 KB	Output is correct
13	Correct	48 ms	8140 KB	Output is correct
14	Correct	41 ms	9204 KB	Output is correct
15	Correct	50 ms	8140 KB	Output is correct
16	Correct	52 ms	8908 KB	Output is correct
17	Correct	43 ms	7884 KB	Output is correct
18	Correct	471 ms	69384 KB	Output is correct
19	Correct	432 ms	69008 KB	Output is correct
20	Correct	537 ms	69716 KB	Output is correct
21	Correct	51 ms	9160 KB	Output is correct
22	Correct	36 ms	8260 KB	Output is correct
23	Correct	118 ms	27588 KB	Output is correct

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	500 KB	Output is correct
2	Correct	52 ms	7704 KB	Output is correct
3	Correct	47 ms	8292 KB	Output is correct
4	Correct	580 ms	69920 KB	Output is correct
5	Correct	47 ms	7504 KB	Output is correct
6	Correct	48 ms	7916 KB	Output is correct
7	Correct	49 ms	9268 KB	Output is correct
8	Correct	48 ms	8736 KB	Output is correct
9	Correct	45 ms	7636 KB	Output is correct
10	Correct	49 ms	8908 KB	Output is correct
11	Correct	47 ms	9172 KB	Output is correct
12	Correct	41 ms	8916 KB	Output is correct
13	Correct	50 ms	7884 KB	Output is correct
14	Correct	513 ms	68556 KB	Output is correct
15	Correct	50 ms	7368 KB	Output is correct
16	Correct	404 ms	69104 KB	Output is correct
17	Correct	488 ms	70052 KB	Output is correct
18	Incorrect	0 ms	344 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	348 KB	Output is correct
2	Correct	5 ms	1244 KB	Output is correct
3	Correct	5 ms	1248 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	0 ms	344 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	344 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	1 ms	344 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	6 ms	1248 KB	Output is correct
17	Correct	50 ms	7892 KB	Output is correct
18	Incorrect	1 ms	348 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Submission #959306

Compilation message