Submission #116450

#	Time	Username	Problem	Language	Result	Execution time	Memory
116450		maruii	Lottery (CEOI18_lot)	C++14	100 / 100	380 ms	8988 KiB

lot

#include <bits/stdc++.h>
using namespace std;

int A[100001], ans[100][100001], idx[100];

int X[100001], B[100001];

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int N, L; cin >> N >> L;
	for (int i = 1; i <= N; ++i) cin >> A[i];
	int Q; cin >> Q;
	pair<int, int> qry[Q];
	for (int i = 0; i < Q; ++i) {
		int x; cin >> x;
		qry[i] = {x, i};
	}

	sort(qry, qry + Q);
	memset(B, -1, sizeof(B));
	for (int i = 0; i < Q; ++i) {
		if (!i || qry[i-1].first != qry[i].first) B[qry[i].first] = i;
		idx[qry[i].second] = i;
	}
	for (int i = L; i; --i)
		if (B[i-1] == -1) B[i-1] = B[i];

	for (int d = 1; d <= N - L; ++d) {
		for (int i = 1; i + d <= N; ++i) {
			X[i] = X[i-1] + (A[i] != A[i + d]);
		}
		for (int i = 1; i + d + L - 1 <= N; ++i) {
			int t = B[X[i + L - 1] - X[i - 1]];
			if (t == -1) continue;
			++ans[t][i];
			++ans[t][i + d];
		}
	}

	for (int i = 1; i < Q; ++i) {
		for (int j = 1; j <= N - L + 1; ++j) {
			if (qry[i].first != qry[i-1].first) ans[i][j] += ans[i-1][j];
			else ans[i][j] = ans[i-1][j];
		}
	}

	for (int i = 0; i < Q; ++i) {
		for (int j = 1; j <= N - L + 1; ++j) cout << ans[idx[i]][j] << ' ';
		cout << '\n';
	}
	return 0;
}

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20