Submission #330265

#	Time	Username	Problem	Language	Result	Execution time	Memory
330265		nandonathaniel	Martian DNA (BOI18_dna)	C++14	68 / 100	2090 ms	13036 KiB

dna

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

int mini[200005],byk[200005];
int s[200005];

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int n,k,r,x,y;
    cin >> n >> k >> r;
    for(int i=1;i<=n;i++)cin >> s[i];
    for(int i=1;i<=r;i++){
    	cin >> x >> y;
    	mini[x]=y;
	}
	int ki=1,ka=n,ans=n+1;
	while(ki<=ka){
		int mid=(ki+ka)/2;
		set<int> valid;
		for(int i=0;i<k;i++){
			if(mini[i]==0)valid.insert(i);
			byk[i]=0;
		}
		for(int i=1;i<=mid;i++){
			byk[s[i]]++;
			if(byk[s[i]]==mini[s[i]])valid.insert(s[i]);
		}
		if(valid.size()==k){
			ans=mid;
			ka=mid-1;
			continue;
		}
		bool ada=false;
		for(int i=mid+1;i<=n;i++){
			byk[s[i-mid]]--;
			if(byk[s[i-mid]]==mini[s[i-mid]]-1)valid.erase(s[i-mid]);
			byk[s[i]]++;
			if(byk[s[i]]==mini[s[i]])valid.insert(s[i]);
			if(valid.size()==k){
				ada=true;
				break;
			}
		}
		if(ada){
			ans=mid;
			ka=mid-1;
		}
		else ki=mid+1;
	}
	if(ans==n+1)cout << "impossible\n";
	else cout << ans << '\n';
	return 0;
}

Compilation message (stderr)

dna.cpp: In function 'int main()':
dna.cpp:28:18: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   28 |   if(valid.size()==k){
      |      ~~~~~~~~~~~~^~~
dna.cpp:39:19: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |    if(valid.size()==k){
      |       ~~~~~~~~~~~~^~~

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