oj.uz

Submission #643564

# Submission time Handle Problem Language Result Execution time Memory
643564 2022-09-22T12:58:26 Z gun_gan Martian DNA (BOI18_dna) C++17
100 / 100
 164 ms 14728 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;

int n, k, m, a[N], b[N], t[N], f[N], lst[N];
vector<int> pos[N];
vector<array<int,3>> ranges;

void update(int idx, int v)
{
	for(int i = idx; i <= n; i += i & -i) f[i] += v;
}

int query(int idx) 
{
	int ret = 0;
	for(int i = idx; i > 0; i -= i & -i) ret += f[i];
	return ret;
}

int sum(int l, int r)
{
	return query(r) - query(l - 1);
}

int main() 
{
	cin.tie(0); ios_base::sync_with_stdio(0);

	cin >> n >> k >> m;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		pos[a[i]].push_back(i);
	}
	for(int i = 0; i < m; i++) {
		int x, v;
		cin >> x >> v;
		for(int j = 0; j + v - 1 < pos[x].size(); j++) {
			ranges.push_back({pos[x][j + v - 1], pos[x][j], x});
		}
	}
	sort(ranges.begin(), ranges.end());
	int ans = 1e9;
	for(auto [r, l, idx] : ranges) {
		if(l > lst[idx]) {
			if(lst[idx] > 0) update(lst[idx], -1);
			lst[idx] = l;
			update(lst[idx], 1);
		}
		int lf = 1, rg = r, z = -1;
		while(lf <= rg) {
			int mid = (lf + rg) / 2;
			if(sum(mid, r) == m) {
				lf = mid + 1, z = mid;
			} else {
				rg = mid - 1;
			}
		}
		// cout << idx << " " << l << " " << r << " " << sum(1, r) << '\n';
		if(z != -1) ans = min(ans, r - z + 1);
	}

	if(ans == 1e9) {
		cout << "impossible";
	} else {
		cout << ans;
	}
}

Compilation message

dna.cpp: In function 'int main()':
dna.cpp:39:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   for(int j = 0; j + v - 1 < pos[x].size(); j++) {
      |                  ~~~~~~~~~~^~~~~~~~~~~~~~~

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 3 ms 5036 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 5028 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 5036 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5076 KB Output is correct
2 Correct 4 ms 5076 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 4 ms 5176 KB Output is correct
5 Correct 5 ms 5076 KB Output is correct
6 Correct 5 ms 5164 KB Output is correct
7 Correct 3 ms 5028 KB Output is correct
8 Correct 2 ms 5024 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 3 ms 5036 KB Output is correct
12 Correct 3 ms 5036 KB Output is correct
13 Correct 3 ms 5032 KB Output is correct
14 Correct 3 ms 5032 KB Output is correct
15 Correct 2 ms 5032 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 9012 KB Output is correct
2 Correct 80 ms 9688 KB Output is correct
3 Correct 96 ms 10244 KB Output is correct
4 Correct 81 ms 9324 KB Output is correct
5 Correct 31 ms 9224 KB Output is correct
6 Correct 20 ms 7376 KB Output is correct
7 Correct 30 ms 8244 KB Output is correct
8 Correct 42 ms 12876 KB Output is correct
9 Correct 24 ms 8192 KB Output is correct
10 Correct 86 ms 9324 KB Output is correct
11 Correct 5 ms 5076 KB Output is correct
12 Correct 4 ms 5076 KB Output is correct
13 Correct 4 ms 5076 KB Output is correct
14 Correct 4 ms 5204 KB Output is correct
15 Correct 3 ms 5076 KB Output is correct
16 Correct 4 ms 5216 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 2 ms 5032 KB Output is correct
19 Correct 3 ms 5028 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 3 ms 5076 KB Output is correct
23 Correct 3 ms 5028 KB Output is correct
24 Correct 2 ms 5028 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 164 ms 12532 KB Output is correct
2 Correct 127 ms 11504 KB Output is correct
3 Correct 61 ms 10100 KB Output is correct
4 Correct 95 ms 10720 KB Output is correct
5 Correct 64 ms 9556 KB Output is correct
6 Correct 103 ms 14728 KB Output is correct
7 Correct 74 ms 9900 KB Output is correct
8 Correct 93 ms 11092 KB Output is correct
9 Correct 67 ms 8940 KB Output is correct
10 Correct 78 ms 9944 KB Output is correct
11 Correct 96 ms 10244 KB Output is correct
12 Correct 83 ms 9320 KB Output is correct
13 Correct 27 ms 9120 KB Output is correct
14 Correct 20 ms 7368 KB Output is correct
15 Correct 22 ms 8172 KB Output is correct
16 Correct 62 ms 12580 KB Output is correct
17 Correct 23 ms 8248 KB Output is correct
18 Correct 80 ms 9360 KB Output is correct
19 Correct 4 ms 5076 KB Output is correct
20 Correct 4 ms 5040 KB Output is correct
21 Correct 5 ms 5076 KB Output is correct
22 Correct 5 ms 5124 KB Output is correct
23 Correct 3 ms 5112 KB Output is correct
24 Correct 4 ms 5164 KB Output is correct
25 Correct 3 ms 4948 KB Output is correct
26 Correct 3 ms 4948 KB Output is correct
27 Correct 3 ms 5032 KB Output is correct
28 Correct 2 ms 4948 KB Output is correct
29 Correct 2 ms 4948 KB Output is correct
30 Correct 2 ms 5032 KB Output is correct
31 Correct 3 ms 5028 KB Output is correct
32 Correct 3 ms 5036 KB Output is correct
33 Correct 3 ms 5032 KB Output is correct