oj.uz

Submission #827436

# Submission time Handle Problem Language Result Execution time Memory
827436 2023-08-16T13:14:39 Z MadokaMagicaFan Lottery (CEOI18_lot) C++14
100 / 100
 466 ms 8484 KB 
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define pb push_back
#define sz(v) ((int)v.size())

const ll inf = 1e16;
const int N = 10000;
const int K = 105;
int n, l, q;

vector<int> nm, v, ks;
vector<array<int, K>> ans;
int j[N], lst[N], e[N], prec[N+1];
int bs(int x) {
	int l, r, m;
	l = 0;
	r = sz(nm);
	while (l < r) {
		m = (l+r)/2;
		if (nm[m] <= x)
			l = m+1;
		else
			r = m;
	}
	return l - 1;
}
int bs2(int x) {
	int l, r, m;
	l = 0;
	r = sz(ks);
	while (l < r) {
		m = (l+r)/2;
		if (ks[m] <= x)
			l = m+1;
		else
			r = m;
	}
	return l;
}

void _add(int x) {
	if (j[x] == 0) return;
	int d = x;
	do {
		d -= j[d];
		++e[x-d];
	} while (j[d]);
}

void _rem(int x) {
	if (j[x] == 0) return;
	int d = x;
	do {
		d -= j[d];
		--e[x-d];
	} while (j[d]);
}

void solve() {
	for (int i = 0; i < n; ++i) {
		j[i] = 0; lst[i] = -1; e[i] = 0;
	}

	for (int i = 0; i < n; ++i) {
		if (lst[v[i]] != -1)
			j[i] = i - lst[v[i]];
		lst[v[i]] = i;
	}
	
	for (int i = 0; i < l; ++i)
		_add(i);

	for (int i = 1; i + l - 1 < n; ++i) {
		_add(i+l-1); _rem(i-1);
		for (int j = 1; j <= i; ++j) {
			if (prec[e[j]]) ans[i][prec[e[j]]-1]++;
		}
	}
}



int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> l;
	v.assign(n, 0);
	ans.resize(n-l+1);
	for (int i = 0; i < n; ++i) cin >> v[i];
	for (int i = 0; i < n - l + 1; ++i)
		for (int j = 0; j < K; ++j) ans[i][j] = 0;
	nm = v; sort(nm.begin(), nm.end()); nm.erase(unique(nm.begin(), nm.end()), nm.end());
	for (int i = 0; i < n; ++i) v[i] = bs(v[i]);
	cin >> q;
	vector<int> qq(q);
	for (int i = 0; i < q; ++i)
		cin>>qq[i];
	for (int i = 0; i < q; ++i)
		ks.pb(l - qq[i]);
	sort(ks.begin(), ks.end()); ks.erase(unique(ks.begin(), ks.end()), ks.end());

	for (int i = 0; i <= n; ++i)
		prec[i] = bs2(i);
	solve();
	reverse(v.begin(), v.end());
	reverse(ans.begin(), ans.end());
	solve();
	reverse(ans.begin(), ans.end());
	for (int i = sz(ks)-1; i >= 0; --i)
		for (int j = 0; j < n - l + 1; ++j)
			ans[j][i] += ans[j][i+1];

	for (int i = 0; i < q; ++i) {
		for (int j = 0; j < n - l + 1; ++j)
			cout << ans[j][bs2(l-qq[i])-1] << (j == n-l ? '\n' : ' ');
	}
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 10 ms 1236 KB Output is correct
14 Correct 6 ms 940 KB Output is correct
15 Correct 5 ms 980 KB Output is correct
16 Correct 6 ms 1132 KB Output is correct
17 Correct 5 ms 1108 KB Output is correct
18 Correct 7 ms 1108 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 4660 KB Output is correct
2 Correct 315 ms 4684 KB Output is correct
3 Correct 122 ms 4664 KB Output is correct
4 Correct 73 ms 4564 KB Output is correct
5 Correct 167 ms 2600 KB Output is correct
6 Correct 60 ms 4380 KB Output is correct
7 Correct 345 ms 2604 KB Output is correct
8 Correct 458 ms 3424 KB Output is correct
9 Correct 94 ms 4524 KB Output is correct
10 Correct 88 ms 4588 KB Output is correct
11 Correct 15 ms 1228 KB Output is correct
12 Correct 90 ms 3404 KB Output is correct
13 Correct 73 ms 2976 KB Output is correct
14 Correct 107 ms 2972 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 4660 KB Output is correct
2 Correct 315 ms 4684 KB Output is correct
3 Correct 122 ms 4664 KB Output is correct
4 Correct 73 ms 4564 KB Output is correct
5 Correct 167 ms 2600 KB Output is correct
6 Correct 60 ms 4380 KB Output is correct
7 Correct 345 ms 2604 KB Output is correct
8 Correct 458 ms 3424 KB Output is correct
9 Correct 94 ms 4524 KB Output is correct
10 Correct 88 ms 4588 KB Output is correct
11 Correct 15 ms 1228 KB Output is correct
12 Correct 90 ms 3404 KB Output is correct
13 Correct 73 ms 2976 KB Output is correct
14 Correct 107 ms 2972 KB Output is correct
15 Correct 466 ms 4524 KB Output is correct
16 Correct 64 ms 4260 KB Output is correct
17 Correct 133 ms 4652 KB Output is correct
18 Correct 68 ms 4620 KB Output is correct
19 Correct 86 ms 4616 KB Output is correct
20 Correct 87 ms 4620 KB Output is correct
21 Correct 68 ms 4620 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 10 ms 1236 KB Output is correct
14 Correct 6 ms 940 KB Output is correct
15 Correct 5 ms 980 KB Output is correct
16 Correct 6 ms 1132 KB Output is correct
17 Correct 5 ms 1108 KB Output is correct
18 Correct 7 ms 1108 KB Output is correct
19 Correct 404 ms 4660 KB Output is correct
20 Correct 315 ms 4684 KB Output is correct
21 Correct 122 ms 4664 KB Output is correct
22 Correct 73 ms 4564 KB Output is correct
23 Correct 167 ms 2600 KB Output is correct
24 Correct 60 ms 4380 KB Output is correct
25 Correct 345 ms 2604 KB Output is correct
26 Correct 458 ms 3424 KB Output is correct
27 Correct 94 ms 4524 KB Output is correct
28 Correct 88 ms 4588 KB Output is correct
29 Correct 15 ms 1228 KB Output is correct
30 Correct 90 ms 3404 KB Output is correct
31 Correct 73 ms 2976 KB Output is correct
32 Correct 107 ms 2972 KB Output is correct
33 Correct 466 ms 4524 KB Output is correct
34 Correct 64 ms 4260 KB Output is correct
35 Correct 133 ms 4652 KB Output is correct
36 Correct 68 ms 4620 KB Output is correct
37 Correct 86 ms 4616 KB Output is correct
38 Correct 87 ms 4620 KB Output is correct
39 Correct 68 ms 4620 KB Output is correct
40 Correct 355 ms 5384 KB Output is correct
41 Correct 32 ms 972 KB Output is correct
42 Correct 121 ms 5388 KB Output is correct
43 Correct 96 ms 4872 KB Output is correct
44 Correct 89 ms 4992 KB Output is correct
45 Correct 397 ms 8420 KB Output is correct
46 Correct 32 ms 1240 KB Output is correct
47 Correct 303 ms 8484 KB Output is correct
48 Correct 143 ms 6608 KB Output is correct
49 Correct 171 ms 7336 KB Output is correct