Submission #891587

#	Time	Username	Problem	Language	Result	Execution time	Memory
891587		jellybean	Martian DNA (BOI18_dna)	C++17	100 / 100	194 ms	17608 KiB

dna

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n,k,r; cin>>n>>k>>r;
	int arr[n];
	map<int,int>m;
	int req[n]={};
	set<int>s;
	for(int i=0; i<n; i++) cin>>arr[i];
	for(int i=0; i<r; i++){
		int a,b; cin>>a>>b;
		req[a]=b;
		s.insert(a);
	}
	int st=0,ans=LLONG_MAX;
	for(int i=0; i<n; i++){
		if(req[arr[i]]) m[arr[i]]++;
		if(m[arr[i]]>=req[arr[i]] and s.find(arr[i])!=s.end()) s.erase(arr[i]);
		while(s.empty()){
			//cout<<st<<" "<<i<<endl;
			ans=min(ans,i-st+1);
			if(req[arr[st]]){
				m[arr[st]]--;
				if(m[arr[st]]<req[arr[st]]) s.insert(arr[st]);
				//if(st==2) cout<<"hi "<<s.size()<<endl;
			}
			st++;
		}
	}
	if(ans==LLONG_MAX) cout<<"impossible";
	else cout<<ans;
	
	return 0;
}

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