Submission #307088

#	Time	Username	Problem	Language	Result	Execution time	Memory
307088		Rainbowbunny	Martian DNA (BOI18_dna)	C++17	100 / 100	70 ms	4600 KiB

dna

#include <bits/stdc++.h>
#define mp make_pair
#define eb emplace_back
#define fi first
#define se second
using namespace std;
using cd = complex <double>;
 
typedef pair <int, int> pii;
const int N = 3e3 + 5;
const long long INF = 1e18;
const int mod = 998244353;//786433;//998244353;
const double Pi = acos(-1);
 
 
void Fastio()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}
 
int n, k, rt;
int a[200005], cnt[200005], b[200005];
 
int main()
{
	Fastio();
	cin >> n >> k >> rt;
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	for(int i = 0; i < rt; i++)
	{
		int temp;
		cin >> temp;
		cin >> b[temp];
	}
	int l = 1, r = n + 1;
	while(l < r)
	{
		int mid = (l + r) >> 1;
		int cc = 0;
		for(int i = 0; i <= k; i++)
		{
			cnt[i] = 0;
		}
		for(int i = 0; i < mid; i++)
		{
			cnt[a[i]]++;
			if(cnt[a[i]] == b[a[i]])
			{
				cc++;
			}
		}
		bool ok = false;
		if(cc == rt)
		{
			ok = true;
		}
		for(int i = mid; i < n; i++)
		{
			if(cnt[a[i - mid]] == b[a[i - mid]])
			{
				cc--;
			}
			cnt[a[i - mid]]--;
			cnt[a[i]]++;
			if(cnt[a[i]] == b[a[i]])
			{
				cc++;
			}
			if(cc == rt or ok == true)
			{
				ok = true;
				break;
			}
		}
		if(ok)
		{
			r = mid;
		}
		else
		{
			l = mid + 1;
		}
	} 	
	if(l == n + 1)
	{
		cout << "impossible";
		return 0;
	}
	cout << l;
}

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