Submission #148093

#	Time	Username	Problem	Language	Result	Execution time	Memory
148093		WhipppedCream	Lottery (CEOI18_lot)	C++17	100 / 100	1438 ms	12280 KiB

lot

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

const int maxn = 1e4+5;

int arr[maxn];
int mark[maxn];

int n;

int k[105];
int tt[105];
int ezreal[105][maxn];
int ans[105][maxn];

int main()
{
	scanf("%d", &n);
	int L; scanf("%d", &L);
	for(int i = 1; i<= n; i++) scanf("%d", arr+i);
	int q;
	scanf("%d", &q);
	for(int i = 1; i<= q; i++) scanf("%d", &k[i]);
	vector< ii > wtf; wtf.pb(ii(-1e9, 0));
	for(int i = 1; i<= q; i++)
	{
		wtf.pb(ii(k[i], i));
	}
	sort(wtf.begin(), wtf.end());
	for(int i = 1; i<= q; i++) tt[i] = wtf[i].X;
	for(int diff = 1; diff<= n-1; diff++)
	{
		memset(mark, 0, sizeof mark);
		int run = 0;
		for(int j = n; j-diff>= 1; j--)
		{
			int i = j-diff;
			if(mark[i]) run--;
			if(arr[i] == arr[j])
			{
				run++;
				if(i-L>= 1) mark[i-L] = true;
			}
			//printf("mis[%d][%d] = %d\n", i, j, L-run);
			if(i+L-1<=n && j+L-1<= n)
			{
				int from = lower_bound(tt+1, tt+q+1, L-run)-tt;
				//printf("from %d (%d %d: %d)\n", from, i, j, L-run);
				ans[from][i]++; ans[from][j]++;
			}
		}
	}
	// for(int i = 1; i<= q; i++)
	// {
	// 	for(int j = 1; j+L-1<= n; j++)
	// 	{
	// 		printf("%d ", ans[i][j]);
	// 	}
	// 	printf("\n");
	// }
	for(int i = 1; i+L-1<= n; i++)
	{
		for(int j = 2; j<= q; j++)
		{
			ans[j][i] += ans[j-1][i];
		}
	}
	for(int i = 1; i<= q; i++)
	{
		for(int j = 1; j+L-1<= n; j++)
		{
			ezreal[wtf[i].Y][j] = ans[i][j];
		}
	}
	for(int i = 1; i<= q; i++)
	{
		for(int j = 1; j+L-1<= n; j++)
		{
			printf("%d ", ezreal[i][j]);
		}
		printf("\n");
	}
}

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", &n);
  ~~~~~^~~~~~~~~~
lot.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int L; scanf("%d", &L);
         ~~~~~^~~~~~~~~~
lot.cpp:25:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i<= n; i++) scanf("%d", arr+i);
                             ~~~~~^~~~~~~~~~~~~
lot.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
lot.cpp:28:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i<= q; i++) scanf("%d", &k[i]);
                             ~~~~~^~~~~~~~~~~~~

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