Submission #895978

#	Time	Username	Problem	Language	Result	Execution time	Memory
895978		pcc	Martian DNA (BOI18_dna)	C++14	68 / 100	34 ms	4668 KiB

dna

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

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const int mxn = 2e5+10;
int cnt[mxn];
int N,K,Q;
int arr[mxn];
int good = 0;
int lim[mxn];

inline void add(int k){
	cnt[k]++;
	if(cnt[k] == lim[k])good++;
	return;
}
inline void del(int k){
	if(cnt[k] == lim[k])good--;
	cnt[k]--;
	return;
}

inline bool check(int len){
	memset(cnt,0,sizeof(cnt));
	good = 0;
	for(int i = 0;i<K;i++){
		if(!lim[i])good++;
	}
	for(int i = 1;i<len;i++){
		add(arr[i]);
	}
	for(int i = len;i<=N;i++){
		add(arr[i]);
		if(good == K)return true;
		del(arr[i-len+1]);
	}
	return false;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>K>>Q;
	for(int i = 1;i<=N;i++)cin>>arr[i];
	while(Q--){
		int a,b;
		cin>>a>>b;
		lim[a] = b;
	}
	int l = 0,r = N;
	while(l != r){
		int mid = (l+r)>>1;
		if(check(mid))r = mid;
		else l = mid+1;
	}
	if(check(l))cout<<l;
	else cout<<"impossible";
}

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