Submission #528731

#	Time	Username	Problem	Language	Result	Execution time	Memory
528731		sidon	Lottery (CEOI18_lot)	C++17	100 / 100	728 ms	8280 KiB

lot

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

const int Z = 10001;

int n, l, q, a[Z], d[Z][102];

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

	cin >> n >> l;

	for(int i = 1; i <= n; ++i)
		cin >> a[i];

	cin >> q;

	int qry[q];
	vector<int> vals = {0, n};

	for(int &i : qry) {
		cin >> i;
		vals.push_back(i);
	}

	sort(begin(vals), end(vals));
	vals.erase(unique(begin(vals), end(vals)), end(vals));

	int C[n+1];

	for(int i = 0; i <= n; ++i)
		C[i] = lower_bound(begin(vals), end(vals), i) - begin(vals);

	for(int j = 1; j + l <= n; ++j) {
		int cur = 0;

		for(int i = 1; i < l; ++i)
			cur += a[i] != a[i+j];

		for(int i = 1; i + j + l - 1 <= n; ++i) {
			cur -= i > 1 && a[i-1] != a[i+j-1];
			cur += a[i+l-1] != a[i+j+l-1];

			++d[i][C[cur]];
			++d[i+j][C[cur]];
		}
	}

	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= 101; ++j)
			d[i][j] += d[i][j-1];

	for(int v : qry) {
		for(int i = 1; i + l - 1 <= n; ++i)
			cout << d[i][C[v]] << ' ';
		cout << '\n';
	}
}

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