Submission #878173

#	Time	Username	Problem	Language	Result	Execution time	Memory
878173		vjudge1	Martian DNA (BOI18_dna)	C++17	100 / 100	28 ms	3920 KiB

dna

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;

int n, k, m;
int a[N], b[N], cnt[N], cont, ans = N;

int main() {
	ios:: sync_with_stdio(0), cin.tie(0);
    cin >> n >> k >> m;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        b[x] = y;
    }
    for (int i = 0; i < k; i++)
        if (!b[i]) cont++;
    for (int l = 0, r = 0; l < n; l++) {
        while (r < n && cont ^ k) {
            cnt[a[r++]]++;
            if (cnt[a[r - 1]] == b[a[r - 1]]) cont++;
        }
        if (cont == k) ans = min(ans, r - l);
        cnt[a[l]]--;
        if (cnt[a[l]] + 1 == b[a[l]]) cont--;
    }
    if (ans == N) cout << "impossible" << '\n';
    else cout << ans << '\n';
	return 0;
}

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