Submission #1305795

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305795		neonglitch	Martian DNA (BOI18_dna)	C++20	100 / 100	1927 ms	11440 KiB

dna

#include <iostream>
#include <set>
using namespace std;
const int N=2e5+10;
int wt[N],cnt[N],val[N];
multiset<int> dif;
// cnt[r]-wt[r] in a 
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,k,r;
	cin>>n>>k>>r;
	for(int i=0;i<n;i++)
	{
		cin>>val[i];
	}
	for(int i=0;i<r;i++)
	{
		int b,q;
		cin>>b>>q;
		wt[b]=q;
	}
	int s=0,e=n+1;
	while(s+1<e)
	{
		int mid=(s+e)/2;
		for(int i=0;i<k;i++)cnt[i]=0;
		dif.clear();
		for(int i=0;i<mid;i++)
		{
			cnt[val[i]]++;
		}
		for(int i=0;i<k;i++)dif.insert(cnt[i]-wt[i]);
		bool pos=0;
		pos|=((*begin(dif))>=0);
		for(int i=mid;i<n;i++)
		{
			int x=val[i];
			dif.erase(dif.find(cnt[x]-wt[x]));
			cnt[x]++;
			dif.insert(cnt[x]-wt[x]);
			x=val[i-mid];
			dif.erase(dif.find(cnt[x]-wt[x]));
			cnt[x]--;
			dif.insert(cnt[x]-wt[x]);
			pos|=((*begin(dif))>=0);
		}
		if(pos)
		{
			e=mid;
		}
		else{
			s=mid;
		}
	}
	if(e==n+1)
	{
		cout<<"impossible"<<endl;
	}
	else
		cout<<e<<endl;
}

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