Submission #70965

#	Time	Username	Problem	Language	Result	Execution time	Memory
70965		MatheusLealV	Lottery (CEOI18_lot)	C++17	100 / 100	1800 ms	9788 KiB

lot

#include <bits/stdc++.h>
#define N 10030
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

pii q[N];

int n, dx, qq, v[N], c, zero[N], k[N], nxt[2*N], id[150];

int pref[N][130];

bool out(int i, int j)
{
	int l = i + dx - 1;

	int r = j + dx - 1;

	if(l > n or r > n or j < 1 or j <= i) return true;;

	return false;
}

inline void solveD(int fl, vector<int>& vet)
{
	int i = 1, j = fl, id;

	c = i - j;

	vet[0] = 0, id = 1;

	while(i <= n and j <= n)
	{
		vet[id] = vet[id - 1] + (v[i] != v[j]);
		
		i ++, j ++, id ++;
	}

	for(int i = 1; i <= n and i != j; i++)
	{
		int l = i + dx - 1, j = i - c;

		if(out(i, j)) continue;

		int dif = vet[l] - vet[i - 1];

		int p = nxt[dif];

		pref[i][p] ++;

		pref[j][p] ++;
	}
}

inline void solveE(int fl, vector<int>& vet)
{
	int i = fl, j = 1;

	int c = i - j, id = 1;

	vet[0] = 0;

	while(i <= n and j <= n)
	{
		vet[id] = vet[id - 1] + (v[i] != v[j]);

		i ++, j ++, id ++;
	}

	for(int i = 1; i <= n; i++)
	{
		int j = i - c;

		int r = j + dx - 1;

		if(out(i, j)) continue;

		int dif = vet[r] - vet[j - 1];

		int p = nxt[dif];

		pref[i][p] ++;

		pref[j][p] ++;
	}
}

inline void init()
{
	sort(q + 1, q + qq + 1);

	for(int i = 1; i <= qq; i++) id[q[i].s] = i;

	for(int i = 0; i < 20060; i++)
	{
		nxt[i] = 110;

		for(int j = 1; j <= qq ; j++)
		{
			if(q[j].f >= i)
			{
				nxt[i] = j;

				break;
			}
		}
	}
}


int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n>>dx;

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

	cin>>qq;

	for(int i = 1, k; i <= qq; i++) cin>>k, q[i] = {k, i};

	init();

	for(int fl = 1; fl <= n; fl ++)
	{
		vector<int> vet(2*n);

		solveE(fl, vet);

		if(fl > 1) solveD(fl, vet);
	}

	for(int i = 1; i <= qq; i++)
	{
		if(i == 1)
		{
			for(int t = 0; t < 130; t++)
				for(int j = 1; j <= n; j++) pref[j][t] += pref[j][t - 1];
		}

		for(int j = 1; j <= n - dx + 1; j++) cout<<pref[j][id[i]]<<" ";

		cout<<"\n";
	}
}

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