Submission #522696

#	Time	Username	Problem	Language	Result	Execution time	Memory
522696		bebecanvas	Martian DNA (BOI18_dna)	C++14	0 / 100	25 ms	5012 KiB

dna

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define endl '\n'

signed main(){
	
	ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n, k, r; cin >> n >> k >> r;
    int a[200005];
    for(int i=0; i<n; i++){cin >> a[i];}
	int b[200005]={0};
	int c[200005];
	for(int i=0; i<k; i++){c[i]=1;}
	for(int i=0; i<r; i++){
		int q, w; cin >> q >> w;
		c[q]= w;
	}
    
    int ans= -1;
    int count= 0;
    int s= 0; int e= 0;
    for(int i=0; i<n; i++){
		b[a[i]]++;
		if(b[a[i]]==c[a[i]]){count++;}
		if(count==k){e= i; ans= e-s+1; break;}
	}
    //cout << ans << endl;
    if(count==k){
		//cout << b[a[s]] << " " << c[a[s]] << endl;
		while(e!=n-1){
			//cout << e << endl;
			while(b[a[s]]>c[a[s]]){
				//cout << "lol" << endl;
				b[a[s]]--;
				s++;
				//cout << "s " << s << endl;
				ans= min(ans, e-s+1);
			}
			e++;
			b[a[e]]++;
			ans= min(ans, e-s+1);
		}
		cout << ans << endl;
	}else{
		cout << "impossible" << endl;
	}
}

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