oj.uz

Submission #1011925

# Submission time Handle Problem Language Result Execution time Memory
1011925 2024-07-01T11:10:27 Z uyt777443 Martian DNA (BOI18_dna) C++17
0 / 100
 192 ms 14236 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;
	} 
	
	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 (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 Incorrect 1 ms 344 KB Output isn't correct
2 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 192 ms 14236 KB Output isn't correct
2 Halted 0 ms 0 KB -