Submission #382519

#	Time	Username	Problem	Language	Result	Execution time	Memory
382519		ritul_kr_singh	Martian DNA (BOI18_dna)	C++17	100 / 100	57 ms	6380 KiB

dna

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << " " <<
#define nl << "\n"

int n, k, r, a[1<<18], b[1<<18];

bool possible(int x){
	int cnt[r], curr = 0;
	for(int i=0; i<r; ++i) cnt[i] = b[i];
	for(int i=0; i<n; ++i){
		if(i-x>=0 and a[i-x]>=0) curr -= ++cnt[a[i-x]]==1;
		if(a[i]>=0) curr += --cnt[a[i]]==0;
		if(curr==r) return true;
	}
	return false;
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> k >> r;
	for(int i=0; i<n; ++i) cin >> a[i];
	vector<int> req(k, 0), id(k, -1);
	for(int i=0, inp; i<r; ++i){
		cin >> inp >> req[inp];
	}
	int currID = 0;
	for(int i=0; i<k; ++i){
		if(req[i]) b[currID] = req[i], id[i] = currID++;
	}
	for(int i=0; i<n; ++i){
		if(req[a[i]]) a[i] = id[a[i]];
		else a[i] = -1;
	}

	if(!possible(n)){
		cout << "impossible" nl;
		return 0;
	}

	int low = 1, high = n;
	while(low<high){
		int mid = (low+high)/2;
		if(possible(mid)) high = mid;
		else low = mid+1;
	}
	cout << low nl;
}

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