oj.uz

Submission #931324

# Submission time Handle Problem Language Result Execution time Memory
931324 2024-02-21T15:24:37 Z armashka Martian DNA (BOI18_dna) C++17
100 / 100
 28 ms 4924 KB 
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 2e5 + 5;
const ll inf = 1e18;

int n, k, R;
int a[N], need[N];
int cnt[N], done, ans = 1e9;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n >> k >> R;
	for (int i = 1; i <= n; ++ i) cin >> a[i];
	for (int i = 1; i <= R; ++ i) {
		int x, y;
		cin >> x >> y;
		need[x] = y;
	}

	int l = 1, r = 0;
	while (r < n) {
		++ r;
		++ cnt[a[r]];
		if (cnt[a[r]] == need[a[r]]) ++ done;

		while (l <= r && done == R) {
			ans = min(ans, r - l + 1);
			
			if (cnt[a[l]] == need[a[l]]) -- done;
			-- cnt[a[l]];
			++ l;
		}
	}
	if (ans == 1e9) cout << "impossible";
	else cout << ans;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2512 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 0 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2516 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2400 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2904 KB Output is correct
2 Correct 10 ms 2884 KB Output is correct
3 Correct 10 ms 2908 KB Output is correct
4 Correct 9 ms 2908 KB Output is correct
5 Correct 13 ms 3932 KB Output is correct
6 Correct 9 ms 2888 KB Output is correct
7 Correct 9 ms 3136 KB Output is correct
8 Correct 14 ms 3928 KB Output is correct
9 Correct 11 ms 3416 KB Output is correct
10 Correct 9 ms 3160 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2532 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 0 ms 2396 KB Output is correct
21 Correct 1 ms 2396 KB Output is correct
22 Correct 1 ms 2512 KB Output is correct
23 Correct 0 ms 2396 KB Output is correct
24 Correct 1 ms 2396 KB Output is correct
25 Correct 1 ms 2396 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4432 KB Output is correct
2 Correct 19 ms 4272 KB Output is correct
3 Correct 15 ms 3908 KB Output is correct
4 Correct 9 ms 2908 KB Output is correct
5 Correct 22 ms 4924 KB Output is correct
6 Correct 28 ms 4696 KB Output is correct
7 Correct 12 ms 3420 KB Output is correct
8 Correct 14 ms 3780 KB Output is correct
9 Correct 9 ms 2908 KB Output is correct
10 Correct 10 ms 2780 KB Output is correct
11 Correct 10 ms 2908 KB Output is correct
12 Correct 9 ms 2924 KB Output is correct
13 Correct 12 ms 3932 KB Output is correct
14 Correct 8 ms 3016 KB Output is correct
15 Correct 9 ms 3164 KB Output is correct
16 Correct 15 ms 3932 KB Output is correct
17 Correct 11 ms 3420 KB Output is correct
18 Correct 9 ms 2908 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Correct 1 ms 2396 KB Output is correct
22 Correct 1 ms 2524 KB Output is correct
23 Correct 1 ms 2396 KB Output is correct
24 Correct 1 ms 2396 KB Output is correct
25 Correct 1 ms 2396 KB Output is correct
26 Correct 1 ms 2396 KB Output is correct
27 Correct 0 ms 2396 KB Output is correct
28 Correct 1 ms 2396 KB Output is correct
29 Correct 1 ms 2516 KB Output is correct
30 Correct 1 ms 2396 KB Output is correct
31 Correct 1 ms 2396 KB Output is correct
32 Correct 0 ms 2396 KB Output is correct
33 Correct 1 ms 2396 KB Output is correct