Submission #656503

#	Time	Username	Problem	Language	Result	Execution time	Memory
656503		MarcosPauloEvers	Lottery (CEOI18_lot)	C++17	100 / 100	498 ms	12864 KiB

lot

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e4 + 10, MAXQ = 110;
int n, len, q;
int arr[MAXN], pos[MAXN];
int ans[MAXN][MAXQ];
int bit[MAXN][MAXQ];
vector< pair<int, int> > qry;

int
main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);

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

	cin >> q;
	for (int i = 1, k; i <= q; i++)
		cin >> k, qry.emplace_back(k, i);

	sort(begin(qry), end(qry));
	memset(pos, 0xff, MAXN * sizeof(int));

	pos[len + 1] = q;
	for (int i = q - 1; i >= 0; i--) pos[qry[i].first] = i;
	for (int i = len; i >= 0; i--) pos[i] = pos[i] == -1 ? pos[i + 1] : pos[i];

	for (int d = 1; d <= n - len; d++) {
		int dist = -1;
		
		for (int i = 1; i + d + len - 1 <= n; i++) {
			if (dist == -1) {
				dist = 0;
				for (int k = 0; k < len; k++)
					dist += arr[i + k] != arr[i + d + k];
			} else dist += arr[i + len - 1] != arr[i + len - 1 + d];

			int j = pos[dist];

			bit[i][j]++;
			bit[i + d][j]++;

			dist -= arr[i] != arr[i + d];
		}
	}

	for (int i = 1; i <= n - len + 1; i++)
		for (int j = 0, acc = 0; j < q; j++)
			acc += bit[i][j], ans[i][qry[j].second] = acc;

	for (int i = 1; i <= q; i++) {
		for (int j = 1; j + len - 1 <= n; j++)
			cout << ans[j][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