Submission #826610

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
826610	2023-08-15T17:59:01 Z	serifefedartar	Martian DNA (BOI18_dna)	C++17	68 / 100	324 ms	1048576 KB

dna

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 1000000007
#define LOGN 20
#define MAXN 100005

vector<vector<int>> pref;
vector<int> DNA;
int main() {
	fast
	int N, K, R;
	cin >> N >> K >> R;

	DNA = vector<int>(N+1);
	for (int i = 1; i <= N; i++)
		cin >> DNA[i];

	pref = vector<vector<int>>(R, vector<int>(N+1, 0));
	vector<pair<int,int>> req(R);
	for (int i = 0; i < R; i++)
		cin >> req[i].f >> req[i].s;

	for (int i = 1; i <= N; i++) {
		for (int ch = 0; ch < R; ch++)
			pref[ch][i] = pref[ch][i-1] + (DNA[i] == req[ch].f);
	}

	int res = 1e7;
	for (int i = 1; i <= N; i++) {
		int ans = 1e7;
		for (int ch = 0; ch < R; ch++) {
			if (pref[ch][i] < req[ch].s)	 {
				ans = -1;
				break;
			}

			int q = upper_bound(pref[ch].begin(), pref[ch].end(), pref[ch][i] - req[ch].s) - pref[ch].begin() - 1;
			ans = min(ans, q);
		}

		if (ans == -1)
			continue;
		else
			res = min(res, i-ans+1);
	}

	if (res == 1e7)
		cout << "impossible\n";
	else
		cout << res-1 << "\n";
}

Subtask #1

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	320 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	316 KB	Output is correct
7	Correct	0 ms	324 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct

Subtask #2

24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	468 KB	Output is correct
3	Correct	1 ms	464 KB	Output is correct
4	Correct	1 ms	468 KB	Output is correct
5	Correct	1 ms	468 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	324 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct

Subtask #3

28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	45 ms	9300 KB	Output is correct
2	Correct	17 ms	3020 KB	Output is correct
3	Correct	81 ms	10124 KB	Output is correct
4	Correct	63 ms	10112 KB	Output is correct
5	Correct	51 ms	10924 KB	Output is correct
6	Correct	24 ms	10052 KB	Output is correct
7	Correct	28 ms	10264 KB	Output is correct
8	Correct	39 ms	10980 KB	Output is correct
9	Correct	57 ms	10580 KB	Output is correct
10	Correct	63 ms	10060 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	468 KB	Output is correct
13	Correct	1 ms	468 KB	Output is correct
14	Correct	1 ms	468 KB	Output is correct
15	Correct	1 ms	484 KB	Output is correct
16	Correct	1 ms	468 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	0 ms	212 KB	Output is correct
22	Correct	1 ms	212 KB	Output is correct
23	Correct	1 ms	212 KB	Output is correct
24	Correct	1 ms	212 KB	Output is correct
25	Correct	0 ms	212 KB	Output is correct

Subtask #4

0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	324 ms	1048576 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-