Submission #689959

#	Time	Username	Problem	Language	Result	Execution time	Memory
689959		NK_	Martian DNA (BOI18_dna)	C++17	100 / 100	115 ms	19956 KiB

dna

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, K, R; cin >> N >> K >> R;

	vector<int> A(N); for(auto& x : A) cin >> x;

	vector<vector<int>> oc(K); for(int i = 0; i < N; i++) oc[A[i]].push_back(i);
	
	vector<int> Q(K, -1); 
	for(int i = 0; i < R; i++) {
		int x, y; cin >> x >> y; Q[x] = --y;
	}

	set<int> S; 
	for(int i = 0; i < K; i++) {
		if (Q[i] == -1) continue;
		if (Q[i] >= int(size(oc[i]))) {
			cout << "impossible" << nl;
			return 0;
		}
		S.insert(oc[i][Q[i]]);
	}

	int ans = N + 1;
	for(int l = 0; l < N; l++) {
		int x = A[l];

		int r = *rbegin(S);
		ans = min(ans, r - l + 1);

		S.erase(oc[x][Q[x]]);
		++Q[x];
		if (Q[x] >= int(size(oc[x]))) break;
		S.insert(oc[x][Q[x]]);
	}

	cout << ans << nl;

    return 0;
}

/*
13 4 3 
1 1 3 2 0 1 2 0 0 0 0 3 1  
0 2
2 1
1 2

5 3 1 
1 2 0 1 2  
0 2

*/

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