Submission #523131

#	Time	Username	Problem	Language	Result	Execution time	Memory
523131		valerikk	Lottery (CEOI18_lot)	C++17	100 / 100	921 ms	8632 KiB

lot

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, l;
	cin >> n >> l;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	
	int q;
	cin >> q;
	vector<int> k(q);
	for (int i = 0; i < q; ++i) {
		cin >> k[i];
	}

	vector<int> ord(q);
	for (int i = 0; i < q; ++i) {
		ord[i] = i;
	}
	sort(ord.begin(), ord.end(), [&](int i, int j) {
		return k[i] < k[j];
	});

	vector<int> first(l + 1, q);
	for (int i = 0; i < q; ++i) {
		first[k[ord[i]]] = min(first[k[ord[i]]], i);
	}
	for (int i = l - 1; i >= 0; --i) {
		first[i] = min(first[i], first[i + 1]);
	}

	vector ans(n, vector<int>(q + 1, 0));
	for (int d = 1; d <= n - l; ++d) {
		vector<int> cnt(n + 1, 0);
		for (int i = 0; i + d < n; ++i) {
			if (a[i] != a[i + d]) {
				++cnt[max(0, i - l + 1)];
				--cnt[i + 1];
			}
		}
		for (int i = 0; i + d + l <= n; ++i) {
			++ans[i][first[cnt[i]]];
			++ans[i + d][first[cnt[i]]];
			cnt[i + 1] += cnt[i];
		}
	}

	for (int i = 0; i < n - l + 1; ++i) {
		for (int j = 0; j < q; ++j) {
			ans[i][j + 1] += ans[i][j];
		}
	}

	vector<int> rev(q);
	for (int i = 0; i < q; ++i) {
		rev[ord[i]] = i;
	}

	for (int i = 0; i < q; ++i) {
		for (int j = 0; j < n - l + 1; ++j) {
			cout << ans[j][rev[i]] << " ";
		}
		cout << "\n";
	}
	return 0;
}

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