Submission #1011927

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011927		uyt777443	Martian DNA (BOI18_dna)	C++17	100 / 100	285 ms	29012 KiB

dna

#include <iostream>
#include <iomanip>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <vector>
#include <utility>
#include <algorithm>
#include <numeric>
#include <string>
#include <cmath>
#include <random>
#include <sstream>
#include <string.h>
#include <assert.h>
#include <limits.h>
using namespace std;

#define fi first
#define se second
#define int long long
#define pb push_back

typedef pair<int,int> ii;

const int INF = 1e18;

map<int, int> cons;

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, k, r; cin >> n >> k >> r;
	vector<int> a(n + 2); for (int i=1; i<=n; i++) cin >> a[i];
	for (int i=1; i<=r; i++) {
		int b, q; cin >> b >> q;
		cons[b] = q;
	} 
	
	queue<int> cur; 
	int cnt = 0; int ans = INF;
	map<int, int> have;
	for (int i=1; i<=n; i++) {
		// cout << ">> " << a[i] << " " << have[a[i]] << " " << cons[a[i]] << '\n';
		cur.push(a[i]), have[a[i]]++; 
   	if (have[a[i]] == cons[a[i]]) cnt++;
		
    if (cnt == r)
			ans = min(ans, (int)cur.size());

		while(!cur.empty() && have[cur.front()] > cons[cur.front()]) {
			have[cur.front()]--; cur.pop();
		}

		if (cnt == r)
			ans = min(ans, (int)cur.size());
		
	}
	if (ans == INF) cout << "impossible";
	else cout << ans;
	return 0;
}

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