Submission #373112

#	Time	Username	Problem	Language	Result	Execution time	Memory
373112		mariowong	Martian DNA (BOI18_dna)	C++14	100 / 100	41 ms	4608 KiB

dna

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

int m,q,n,ans,l,r,u,v,ct[200005],now[200005],ok,a[200005]; 
int main(){
	ios::sync_with_stdio(false);
	cin >> n >> m >> q;
	for (int i=1;i<=n;i++){
		cin >> a[i];
	}
	for (int i=1;i<=q;i++){
		cin >> u >> v;
		ct[u]=v;
	}
	l=1; r=0; ans=1e9;
	while (l <= n && r <= n){
		if (ok == q){
			ans=min(ans,r-l+1);
			if (now[a[l]] == ct[a[l]])
			ok--;
			now[a[l]]--;
			l++;
		}
		else
		{
			r++;
			now[a[r]]++;
			if (now[a[r]] == ct[a[r]])
			ok++;
		}
	}
	if (ans == 1e9)
	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