Submission #453774

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
453774	2021-08-04T18:42:53 Z	Hamed5001	Martian DNA (BOI18_dna)	C++14	100 / 100	1249 ms	3716 KB

dna

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int mxN = 2e5+10;
int N, K, R;

void solve() {
	cin >> N >> K >> R;
	vector<int> DNA(N), need(K, INT_MAX);

	for (auto& dna : DNA) 
		cin >> dna;

	for (int i = 0; i < R; i++) {
		int B, Q;
		cin >> B >> Q;
		need[B] = Q; 
	}

	int ans = INT_MAX;
	int good = 0;
	for (int l = 0, r = 0; l < N; l++) {
		while(good < R && r < N) {
			if (--need[DNA[r++]] == 0)
				++good;
		}

		if (good == R) {
			cerr << l << ' ' << r << endl;
			ans = min(ans, r - l);
		}

		if (++need[DNA[l]] == 1) {
			--good;
		}
	}

	cout << (ans == INT_MAX ? "impossible" : to_string(ans));
}	

int main() {

	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}

Subtask #1

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 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	0 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	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct

Subtask #2

24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	332 KB	Output is correct
2	Correct	11 ms	332 KB	Output is correct
3	Correct	9 ms	352 KB	Output is correct
4	Correct	18 ms	356 KB	Output is correct
5	Correct	11 ms	344 KB	Output is correct
6	Correct	21 ms	352 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	0 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct

Subtask #3

28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	626 ms	2376 KB	Output is correct
2	Correct	920 ms	3012 KB	Output is correct
3	Correct	1227 ms	3628 KB	Output is correct
4	Correct	819 ms	2712 KB	Output is correct
5	Correct	736 ms	2872 KB	Output is correct
6	Correct	17 ms	1100 KB	Output is correct
7	Correct	18 ms	1100 KB	Output is correct
8	Correct	683 ms	3212 KB	Output is correct
9	Correct	732 ms	2564 KB	Output is correct
10	Correct	771 ms	2672 KB	Output is correct
11	Correct	19 ms	332 KB	Output is correct
12	Correct	13 ms	460 KB	Output is correct
13	Correct	9 ms	344 KB	Output is correct
14	Correct	17 ms	352 KB	Output is correct
15	Correct	10 ms	344 KB	Output is correct
16	Correct	21 ms	332 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct
19	Correct	0 ms	204 KB	Output is correct
20	Correct	0 ms	204 KB	Output is correct
21	Correct	0 ms	204 KB	Output is correct
22	Correct	1 ms	204 KB	Output is correct
23	Correct	0 ms	204 KB	Output is correct
24	Correct	1 ms	204 KB	Output is correct
25	Correct	1 ms	204 KB	Output is correct

Subtask #4

32.0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	754 ms	2896 KB	Output is correct
2	Correct	833 ms	2972 KB	Output is correct
3	Correct	834 ms	2932 KB	Output is correct
4	Correct	1214 ms	3716 KB	Output is correct
5	Correct	40 ms	1484 KB	Output is correct
6	Correct	591 ms	2876 KB	Output is correct
7	Correct	62 ms	1100 KB	Output is correct
8	Correct	507 ms	2220 KB	Output is correct
9	Correct	626 ms	2328 KB	Output is correct
10	Correct	921 ms	3004 KB	Output is correct
11	Correct	1249 ms	3632 KB	Output is correct
12	Correct	826 ms	2828 KB	Output is correct
13	Correct	798 ms	2932 KB	Output is correct
14	Correct	17 ms	1104 KB	Output is correct
15	Correct	18 ms	1100 KB	Output is correct
16	Correct	659 ms	3312 KB	Output is correct
17	Correct	747 ms	2560 KB	Output is correct
18	Correct	768 ms	2640 KB	Output is correct
19	Correct	19 ms	332 KB	Output is correct
20	Correct	10 ms	332 KB	Output is correct
21	Correct	9 ms	332 KB	Output is correct
22	Correct	17 ms	368 KB	Output is correct
23	Correct	10 ms	332 KB	Output is correct
24	Correct	22 ms	332 KB	Output is correct
25	Correct	1 ms	204 KB	Output is correct
26	Correct	1 ms	204 KB	Output is correct
27	Correct	0 ms	204 KB	Output is correct
28	Correct	0 ms	204 KB	Output is correct
29	Correct	0 ms	204 KB	Output is correct
30	Correct	1 ms	204 KB	Output is correct
31	Correct	1 ms	204 KB	Output is correct
32	Correct	1 ms	204 KB	Output is correct
33	Correct	1 ms	204 KB	Output is correct