Submission #1010386

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010386		uyt777443	Martian DNA (BOI18_dna)	C++17	0 / 100	267 ms	19276 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;
	} 
	// cout << "HERE\n";

	queue<int> cur; map<int, int> rem;
	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';
		if (cons.count(a[i]) && have[a[i]] < cons[a[i]]) {
			cur.push(a[i]), have[a[i]]++; if (have[a[i]] == cons[a[i]]) cnt++;
		}
		else {
			have[a[i]]++; cur.push(a[i]); 
			if (cur.front() == a[i])
				cur.pop(), have[a[i]]--;
			else  
				rem[a[i]]++;	
		}
		if (cnt == r)
			ans = min(ans, (int)cur.size());
		
		while(!cur.empty() && rem[cur.front()] > 0) {
			rem[cur.front()]--; have[cur.front()]--; cur.pop();	
		}
	}
	if (ans == INF) cout << "impossible";
	else cout << ans;
	return 0;
}

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