oj.uz

Submission #959307

# Submission time Handle Problem Language Result Execution time Memory
959307 2024-04-07T23:23:25 Z NK_ Strange Device (APIO19_strange_device) C++17
35 / 100
 581 ms 65524 KB 
// 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(array<ll, 2>{l, +1});
		E.pb(array<ll, 2>{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 && 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 4 ms 1292 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 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 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 1 ms 344 KB Output is correct
12 Correct 1 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 0 ms 348 KB Output is correct
16 Correct 4 ms 1368 KB Output is correct
17 Correct 53 ms 7636 KB Output is correct
18 Incorrect 1 ms 344 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 600 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 1 ms 348 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 348 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 311 ms 51216 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 452 KB Output is correct
2 Correct 453 ms 61028 KB Output is correct
3 Correct 463 ms 60052 KB Output is correct
4 Correct 415 ms 60000 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 452 KB Output is correct
2 Correct 453 ms 61028 KB Output is correct
3 Correct 463 ms 60052 KB Output is correct
4 Correct 415 ms 60000 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 451 ms 60052 KB Output is correct
7 Correct 470 ms 60048 KB Output is correct
8 Correct 448 ms 64240 KB Output is correct
9 Correct 527 ms 65524 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 452 KB Output is correct
2 Correct 453 ms 61028 KB Output is correct
3 Correct 463 ms 60052 KB Output is correct
4 Correct 415 ms 60000 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 43 ms 8768 KB Output is correct
7 Correct 45 ms 8916 KB Output is correct
8 Correct 47 ms 9280 KB Output is correct
9 Correct 51 ms 8208 KB Output is correct
10 Correct 40 ms 7632 KB Output is correct
11 Correct 44 ms 8136 KB Output is correct
12 Correct 39 ms 7624 KB Output is correct
13 Correct 50 ms 8040 KB Output is correct
14 Correct 43 ms 9160 KB Output is correct
15 Correct 52 ms 8656 KB Output is correct
16 Correct 48 ms 8916 KB Output is correct
17 Correct 42 ms 8904 KB Output is correct
18 Correct 450 ms 61264 KB Output is correct
19 Correct 427 ms 60472 KB Output is correct
20 Correct 537 ms 60172 KB Output is correct
21 Correct 49 ms 8400 KB Output is correct
22 Correct 36 ms 7884 KB Output is correct
23 Correct 116 ms 26356 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 51 ms 8548 KB Output is correct
3 Correct 50 ms 7116 KB Output is correct
4 Correct 581 ms 60048 KB Output is correct
5 Correct 46 ms 9172 KB Output is correct
6 Correct 47 ms 7932 KB Output is correct
7 Correct 46 ms 7880 KB Output is correct
8 Correct 49 ms 8140 KB Output is correct
9 Correct 45 ms 8384 KB Output is correct
10 Correct 49 ms 7892 KB Output is correct
11 Correct 46 ms 8096 KB Output is correct
12 Correct 50 ms 8404 KB Output is correct
13 Correct 48 ms 8392 KB Output is correct
14 Correct 509 ms 50732 KB Output is correct
15 Correct 50 ms 7620 KB Output is correct
16 Correct 427 ms 60152 KB Output is correct
17 Correct 461 ms 60136 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 1 ms 348 KB Output is correct
2 Correct 4 ms 1292 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 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 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 1 ms 344 KB Output is correct
12 Correct 1 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 0 ms 348 KB Output is correct
16 Correct 4 ms 1368 KB Output is correct
17 Correct 53 ms 7636 KB Output is correct
18 Incorrect 1 ms 344 KB Output isn't correct
19 Halted 0 ms 0 KB -