Submission #259924

#	Time	Username	Problem	Language	Result	Execution time	Memory
259924		pedroslrey	Lottery (CEOI18_lot)	C++17	100 / 100	1688 ms	8512 KiB

lot

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e4 + 10;
const int MAXQ = 1e2 + 10;

int xs[MAXN];
int ans[MAXQ][MAXN];
int rev[MAXQ];
vector<pair<int, int>> queries;

void calc(int n, int l) {
	for (int space = 1; space + l - 1 < n; ++space) {
		int diffs = 0;
		for (int i = 0; i < l; ++i)
		if (xs[i] != xs[i + space])
				++diffs;

		int idx = lower_bound(queries.begin(), queries.end(), make_pair(diffs, 0)) - queries.begin();
		++ans[idx][0];
		++ans[idx][space];

		for (int i = 1; i + space + l - 1 < n; ++i) {
			if (xs[i-1] != xs[i + space - 1])
				--diffs;
	
			if (xs[i + l - 1] != xs[i + l + space - 1])
				++diffs;
	
			int idx = lower_bound(queries.begin(), queries.end(), make_pair(diffs, 0)) - queries.begin();
			++ans[idx][i];
			++ans[idx][i + space];
		}
	}
}

int main() {
	int n, l;
	scanf("%d%d", &n, &l);

	for (int i = 0; i < n; ++i)
		scanf("%d", &xs[i]);

	int q;
	scanf("%d", &q);
	for (int i = 0; i < q; ++i) {
		int k;
		scanf("%d", &k);

		queries.push_back({k, i});
	}

	sort(queries.begin(), queries.end());

	calc(n, l);

	for (int i = 0; i < q; ++i)
		rev[queries[i].second] = i;

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

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

Compilation message (stderr)

lot.cpp: In function 'int main()':
lot.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &l);
  ~~~~~^~~~~~~~~~~~~~~~
lot.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &xs[i]);
   ~~~~~^~~~~~~~~~~~~~
lot.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
lot.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &k);
   ~~~~~^~~~~~~~~~

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