Submission #1123762

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123762		sigmaohiogyattrip	Martian DNA (BOI18_dna)	C++17	100 / 100	65 ms	5960 KiB

dna

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

#define ll long long
#define ull unsigned long long
#define pll pair<ll,ll>
#define qll queue<ll>
#define inf LLONG_MAX
#define test return 12;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll n,k,r;cin>>n>>k>>r;
	ll c[n]; qll q;
	for(ll i=0;i<n;i++) {
		c[i];cin>>c[i];
	}
	ll cnt[k],req[k]; fill(req,req+k,0); fill(cnt,cnt+k,0); 
	for(ll i=0;i<r;i++) {
		ll a,b;cin>>a>>b;
		req[a]=b;
	}
	
	ll lo=0,hi=n+1;
	while(lo<hi-1){
		ll x = (hi+lo)/2;
		qll q;
		ll satis=0;
		bool flag=0;//satis??
		fill(cnt,cnt+k,0); 
		for(ll i=0;i<x;i++) {
			q.push(c[i]);
			cnt[c[i]]++;
			if(cnt[c[i]]==req[c[i]] and req[c[i]]!=0)satis++;
			if(satis==r)flag=1;
		}
		for(ll i=x;i<n;i++) {
			cnt[q.front()]--;
			if(cnt[q.front()]==req[q.front()]-1)satis--;
			q.pop();
			
			q.push(c[i]);
			cnt[c[i]]++;
			if(cnt[c[i]]==req[c[i]])satis++;
			if(satis==r)flag=1;
		}
		cerr<<x<<"satis"<<satis<<endl;
		if(!flag){
			lo=x;
		} else{
			hi=x;
		}
	}
	if(hi==n+1){
		cout<<"impossible";
		return 0;
	}
	cout<<hi;
	
	
}
		

	

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