Submission #1129673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129673		Muhammet	Martian DNA (BOI18_dna)	C++20	100 / 100	159 ms	137376 KiB

dna

#include "bits/stdc++.h"

using namespace std;

#define SZ(s) (int)s.size()

int n, k, r;

int main(){
	ios::sync_with_stdio(false); cin.tie(nullptr);

	cin >> n >> k >> r;
	vector <int> a(n+1), vis(k+1,0), vis1(k+1,0);
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	for(int i = 1; i <= r; i++){
		int b, q1;
		cin >> b >> q1;
		vis1[b] = 1;
		vis[b] = q1;
	}
	int r1 = r, ind = 0, ans = n+1;
	queue <int> q[k+1];
	set <int> s;
	for(int i = 1; i <= n; i++){
		if(!vis1[a[i]]) continue;
		if(!vis[a[i]]){
			s.erase(s.find(q[a[i]].front()));
			q[a[i]].pop();
			q[a[i]].push(i);
			s.insert(q[a[i]].front());
			if(r1 == 0) ans = min(ans, i-(*s.begin())+1);
			continue;
		}
		vis[a[i]]--;
		if(vis[a[i]] == 0) r1--;
		if(SZ(q[a[i]]) == 0) s.insert(i);
		q[a[i]].push(i);
		if(r1 == 0) ans = min(ans, i-(*s.begin())+1);
	}
	if(ans == n+1) cout << "impossible";
	else cout << ans;
}

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