Submission #528730

#	Time	Username	Problem	Language	Result	Execution time	Memory
528730		sidon	Lottery (CEOI18_lot)	C++17	100 / 100	843 ms	8496 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));

	for(int j = 1; j + l <= n; ++j) {
		int cur = 0, pt = 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];

			while(vals[pt] < cur) ++pt;
			while(pt && vals[pt-1] >= cur) --pt;

			++d[i][pt];
			++d[i+j][pt];
		}
	}

	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) {
		int j = lower_bound(begin(vals), end(vals), v) - begin(vals);

		for(int i = 1; i + l - 1 <= n; ++i)
			cout << d[i][j] << ' ';
		cout << '\n';
	}
}

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