oj.uz

Submission #639528

# Submission time Handle Problem Language Result Execution time Memory
639528 2022-09-10T12:39:51 Z flappybird Martian DNA (BOI18_dna) C++17
100 / 100
 71 ms 15884 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 201010
#define MAXS 20
#define INF 1000000010
#define bb ' '
#define ln '\n'
#define Ln '\n'
int arr[MAX];
int ne[MAX];
int num[MAX];
vector<int> v[MAX];
int cnt[MAX];
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N, K, R;
	cin >> N >> K >> R;
	int i;
	for (i = 1; i <= N; i++) cin >> arr[i], v[arr[i]].push_back(i);
	int a, b;
	int mx = 1;
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	for (i = 1; i <= R; i++) {
		cin >> a >> b;
		num[a] = b;
		if (b > v[a].size()) {
			cout << "impossible" << ln;
			return 0;
		}
		pq.emplace(v[a][0], a);
		mx = max(mx, v[a][num[a] - 1]);
	}
	int ans = N;
	while (1) {
		int t = pq.top().second;
		ans = min(ans, mx - pq.top().first + 1);
		pq.pop();
		if (cnt[t] + num[t] == v[t].size()) {
			cout << ans << ln;
			return 0;
		}
		cnt[t]++;
		mx = max(v[t][cnt[t] + num[t] - 1], mx);
		pq.emplace(v[t][cnt[t]], t);
	}
	cout << ans << ln;
}

Compilation message

dna.cpp: In function 'int main()':
dna.cpp:33:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   if (b > v[a].size()) {
      |       ~~^~~~~~~~~~~~~
dna.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   if (cnt[t] + num[t] == v[t].size()) {
      |       ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 4 ms 4948 KB Output is correct
5 Correct 4 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 5056 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5156 KB Output is correct
5 Correct 4 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 4 ms 5056 KB Output is correct
8 Correct 3 ms 5056 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 7124 KB Output is correct
2 Correct 15 ms 6928 KB Output is correct
3 Correct 18 ms 6740 KB Output is correct
4 Correct 17 ms 7128 KB Output is correct
5 Correct 31 ms 8488 KB Output is correct
6 Correct 14 ms 7380 KB Output is correct
7 Correct 16 ms 7328 KB Output is correct
8 Correct 52 ms 13336 KB Output is correct
9 Correct 24 ms 8064 KB Output is correct
10 Correct 18 ms 7328 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 3 ms 5132 KB Output is correct
14 Correct 4 ms 5204 KB Output is correct
15 Correct 3 ms 5076 KB Output is correct
16 Correct 3 ms 5076 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 4 ms 5076 KB Output is correct
19 Correct 4 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 3 ms 5056 KB Output is correct
22 Correct 3 ms 4948 KB Output is correct
23 Correct 3 ms 5056 KB Output is correct
24 Correct 3 ms 4988 KB Output is correct
25 Correct 3 ms 4948 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 9708 KB Output is correct
2 Correct 56 ms 8920 KB Output is correct
3 Correct 39 ms 9868 KB Output is correct
4 Correct 21 ms 7188 KB Output is correct
5 Correct 42 ms 10312 KB Output is correct
6 Correct 71 ms 15884 KB Output is correct
7 Correct 25 ms 8376 KB Output is correct
8 Correct 38 ms 9048 KB Output is correct
9 Correct 15 ms 7516 KB Output is correct
10 Correct 16 ms 7356 KB Output is correct
11 Correct 17 ms 7256 KB Output is correct
12 Correct 17 ms 7508 KB Output is correct
13 Correct 39 ms 9672 KB Output is correct
14 Correct 20 ms 7392 KB Output is correct
15 Correct 19 ms 7368 KB Output is correct
16 Correct 39 ms 13396 KB Output is correct
17 Correct 23 ms 8120 KB Output is correct
18 Correct 18 ms 7356 KB Output is correct
19 Correct 3 ms 5088 KB Output is correct
20 Correct 3 ms 5072 KB Output is correct
21 Correct 3 ms 5088 KB Output is correct
22 Correct 3 ms 5216 KB Output is correct
23 Correct 3 ms 5088 KB Output is correct
24 Correct 3 ms 5076 KB Output is correct
25 Correct 3 ms 5064 KB Output is correct
26 Correct 3 ms 4960 KB Output is correct
27 Correct 3 ms 4960 KB Output is correct
28 Correct 5 ms 4960 KB Output is correct
29 Correct 4 ms 5012 KB Output is correct
30 Correct 3 ms 4960 KB Output is correct
31 Correct 3 ms 4948 KB Output is correct
32 Correct 3 ms 5056 KB Output is correct
33 Correct 3 ms 4948 KB Output is correct