Submission #927119

#	Time	Username	Problem	Language	Result	Execution time	Memory
927119		vjudge1	Martian DNA (BOI18_dna)	C++17	0 / 100	259 ms	34404 KiB

dna

#include <bits/stdc++.h>

using namespace std;

#define all(a) a.begin(),a.end()
#define pb push_back
#define vt vector
#define endl '\n'
typedef long long ll;

const ll mod=1e9+7;
const ll inf=1e9+7;
const int N=5e5+4;

int n,k,r;
int a[N];
map<int,int>mp,cur;
set<int>st[N];
multiset<int>mst;

void solve(){
	cin>>n>>k>>r;
	for(int i=1; i<=n; ++i){
		cin>>a[i];
	}
	ll all=0;
	for(int i=1; i<=r; ++i){
		int tp,cn;
		cin>>tp>>cn;
		mp[tp]=cn;
		for(int x=0; x<cn; ++x) {
			mst.insert(tp);
			++all;
			if(all>n){
				cout<<"i	mpossible\n";
				return;
			}
		}
	}
	int l=1,r=1;
	int ans=inf;
	while(1){
		//cout<<l<<' '<<r<<endl;
		//cout<<mst.size()<<endl;
		while(r<=n && mst.size()){
			auto pos=mst.find(a[r]);
			cur[a[r]]++;
			//cout<<a[r]<<"  "<<cur[a[r]]<<endl;
			if(pos!=mst.end()) mst.erase(pos);
			++r;
		}
		if(r>n) break;
		ans=min(ans,r-l+1);
		while(l<r){
			while(l<r && mp[a[l]]==0) ++l;
			ans=min(ans,r-l);
			cur[a[l]]--;
			//cout<<a[l]<<' '<<cur[a[l]]<<endl;
		//	return;
			if(cur[a[l]]<mp[a[l]]) {
				mst.insert(a[l]);
				++l;
				break;
			}
			++l;
			ans=min(ans,r-l);
		}
	}
	if(ans==inf){
		cout<<"impossible\n";
		return;
	}
	cout<<ans<<endl;
}
			
int main(){
	int tt=1;
	//cin>>tt;
	while(tt--) {
		solve();
	}
}

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