| # | Time | Username | Problem | Language | Result | Execution time | Memory | 
|---|---|---|---|---|---|---|---|
| 1123844 | fiips | Martian DNA (BOI18_dna) | C++20 | 0 ms | 0 KiB | 
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	int n, k, ri;
	cin >> n >> k >> ri;
	
	int dna[n];
	for(int i = 0; i < n; i++) cin >> dna[i];
	
	int req[k];
	for(int i = 0; i < k; i++) req[i] = LLONG_MAX / 20; 
	
	for(int i = 0; i < ri; i++) {
		int a, b;
		cin >> a >> b;
		req[a] = b;
	}
	
	int cnt[k];
	memset(cnt, 0, sizeof(cnt));
	
	unordered_set<int> s;
	
	int ans = LLONG_MAX / 20, l = 0;
	for(int r = 0; r < n; r++) {
		cnt[dna[r]]++;
		if(cnt[dna[r]] >= req[dna[r]]) s.emplace(dna[r]);
		
		if(s.size() == ri){
            while(1){
			    cnt[dna[l]]--;
			    if(cnt[dna[l]] < req[dna[l]]) {
                    s.erase(dna[l]); 
                    break;
				}
			
			    ans = min(r - l + 1, ans); 
			    l++;
			}
		}
	}
	
	if(ans == LLONG_MAX / 20) cout << "impossible";
	else cout << ans;
