Submission #1013742

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013742		vjudge1	Martian DNA (BOI18_dna)	C++17	0 / 100	18 ms	3164 KiB

dna

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;

const int N = 2e5+1, INF = 1e9;

int n, k, r;
int a[N];
int q[N];

int cur[N];

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> n >> k >> r;
	for (int i = 1; i <= n; cin >> a[i++]);
	for (int i = 1, b; i <= r; cin >> b >> q[b], i++);
	int sat = (++cur[a[1]] == 1);
	int l = 1, r = 1;
	int sol = INF;
	while (r <= n) {
		if (sat == k && l < r) {
			sol = min(sol, r-l+1);
			cur[a[l]]--;
			if (cur[a[l]] == q[a[l]]-1) sat--;
			l++;
		} else {
			r++;
			cur[a[r]]++;
			if (cur[a[r]] == q[a[r]]) sat++;
		}
	}
	cout << (sol == INF ? "impossible" : to_string(sol));
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 24
• Subtask 3: 0 / 28
• Subtask 4: 0 / 32