Submission #617166

#	Time	Username	Problem	Language	Result	Execution time	Memory
617166		usuyus	Lottery (CEOI18_lot)	C++14	100 / 100	2400 ms	8228 KiB

lot

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

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

	int n, l; scanf("%d %d", &n, &l);
	vector<int> a(n);
	for (int &x : a) scanf("%d", &x);

	int q; scanf("%d", &q);
	vector<int> qs(q);
	for (int &x : qs) scanf("%d", &x), x = l-x;

	vector<int> qidx(q);
	iota(qidx.begin(), qidx.end(), 0);
	sort(qidx.begin(), qidx.end(), [&] (int i, int j) {
		return qs[i] < qs[j];
	});

	vector<vector<int>> ans(q, vector<int>(n-l+1));
	deque<int> sim(n+1); // offset by l -- sim[i] actually is sim[i-l]
	vector<int> cnts(l);

	for (int i=-l; i<=n-l; i++) {
		sim.pop_back();
		sim.push_front(0);

		if (0 <= i-1 && i-1 < n)
			for (int j=1; j<=n-l; j++)
				sim[j+l] -= (a[i-1] == a[j-1]);

		if (0 <= i+l-1 && i+l-1 < n)
			for (int j=-(l-1); j<n-(l-1); j++)
				sim[j+l] += (a[i + (l-1)] == a[j + (l-1)]);

		if (i >= 0) {
			for (int j=l; j<=n; j++) ++cnts[sim[j]];

			int cur = 0, cnt = n-l+1;
			for (int j : qidx) {
				for (; cur < qs[j]; cur++) cnt -= cnts[cur];
				ans[j][i] = cnt - 1;
			}

			for (int j=l; j<=n; j++) --cnts[sim[j]];
		}
	}

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

Compilation message (stderr)

lot.cpp: In function 'int main()':
lot.cpp:7:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |  int n, l; scanf("%d %d", &n, &l);
      |            ~~~~~^~~~~~~~~~~~~~~~~
lot.cpp:9:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |  for (int &x : a) scanf("%d", &x);
      |                   ~~~~~^~~~~~~~~~
lot.cpp:11:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |  int q; scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~
lot.cpp:13:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  for (int &x : qs) scanf("%d", &x), x = l-x;
      |                    ~~~~~^~~~~~~~~~

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