Submission #112954

#	Time	Username	Problem	Language	Result	Execution time	Memory
112954		luciocf	Lottery (CEOI18_lot)	C++14	100 / 100	688 ms	8568 KiB

lot

#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

const int maxn = 1e4+10;
const int maxq = 110;

typedef pair<int, int> pii;

int a[maxn];

int first[maxn];
int ans[maxn][maxq];

pii query[maxq];

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

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

	int q;
	scanf("%d", &q);

	for (int i = 1; i <= q; i++)
	{
		scanf("%d", &query[i].ff);
		query[i].ss = i;
	}

	sort(query+1, query+q+1);

	for (int i = 0; i <= l; i++)
	{
		first[i] = q+1;

		for (int j = 1; j <= q; j++)
		{
			if (query[j].ff >= i)
			{
				first[i] = query[j].ss;
				break;
			}
		}
	}

	for (int i = 1; i+l-1 <= n; i++)
	{
		int at = 0;
		for (int j = 1; j <= l; j++)
			if (a[i+j-1] != a[j])
				at++;

		if (i != 1)
		{
			ans[1][first[at]]++;
			ans[i][first[at]]++;
		}

		for (int j = 2; j+l-1 <= n; j++)
		{
			int pos = i+j-1;
			if (pos+l-1 > n) break;

			if (a[j-1] != a[pos-1]) at--;

			if (a[j+l-1] != a[pos+l-1]) at++;

			if (j != pos)
			{
				ans[j][first[at]]++;
				ans[pos][first[at]]++;
			}
		}
	}

	for (int i = 1; i <= q; i++)
		for (int j = 1; j <= n; j++)
			ans[j][query[i].ss] += ans[j][query[i-1].ss];

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

Compilation message (stderr)

lot.cpp: In function 'int main()':
lot.cpp:23: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:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~
lot.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
lot.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &query[i].ff);
   ~~~~~^~~~~~~~~~~~~~~~~~~~

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