Submission #759019

#	Time	Username	Problem	Language	Result	Execution time	Memory
759019		ymm	Martian DNA (BOI18_dna)	C++17	100 / 100	25 ms	3792 KiB

dna

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 200'010;
int a[N], cnt[N];
int n, k, r;

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> k >> r;
	Loop (i,0,n)
		cin >> a[i];
	Loop (i,0,r) {
		int b, q;
		cin >> b >> q;
		cnt[b] = q;
	}
	int ans = n+1;
	int p = 0;
	int pos = r;
	Loop (i,0,n) {
		while (pos) {
			if (p == n)
				goto end;
			cnt[a[p]]--;
			pos -= cnt[a[p]] == 0;
			++p;
		}
		ans = min<int>(ans, p - i);
		pos += cnt[a[i]] == 0;
		cnt[a[i]]++;
	}
end:
	if (ans == n+1)
		cout << "impossible\n";
	else
		cout << ans << '\n';
}

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