oj.uz

Submission #1010377

# Submission time Handle Problem Language Result Execution time Memory
1010377 2024-06-29T02:37:13 Z uyt777443 Martian DNA (BOI18_dna) C++17
0 / 100
 231 ms 19356 KB 
#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> rem_until, 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();
			else  
				rem[a[i]]++;
			
		}
		if (cnt == r)
			ans = min(ans, (int)cur.size());
		
		while(!cur.empty() && rem[cur.front()] > 0) {
			rem[cur.front()]--; cur.pop();
		}

	}
	if (ans == INF) cout << "impossible";
	else cout << ans;
	return 0;
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 3164 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 231 ms 19356 KB Output isn't correct
2 Halted 0 ms 0 KB -