Submission #570195

#	Time	Username	Problem	Language	Result	Execution time	Memory
570195		MarcosPauloEvers	Lottery (CEOI18_lot)	C++17	45 / 100	3075 ms	4944 KiB

lot

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e4 + 10, MAXQ = 110;
int n, l, q;
int arr[MAXN];
int bit[MAXN][MAXQ];
int ans[MAXQ][MAXN];
vector<pair<int, int> > qry;

int
get(int i, int p)
{
	int sum = 0;
	for(; 0 < p && p < MAXQ; p -= p & -p)
		sum += bit[i][p];
	return sum;
}

void
add(int i, int p)
{
	for(; 0 < p && p < MAXQ; p += p & -p)
		bit[i][p]++;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> l;
	for(int i = 0; i < n; i++)
		cin >> arr[i];

	cin >> q;
	for(int i = 0, k; i < q; i++)
		cin >> k, qry.emplace_back(k, i);
	
	sort(begin(qry), end(qry));
	for(int i = 0; i <= n - l; i++)
	{
		for(int j = 0; j < i; j++)
		{
			int dst = 0;
			for(int k = 0; k < l; k++)
				dst += arr[i + k] != arr[j + k];
			int qtd = lower_bound(begin(qry), end(qry), make_pair(dst, 0)) - begin(qry);

			add(i, qtd + 1);
			add(j, qtd + 1);
		}
	}
	for(int i = 0; i < q; i++)
		for(int j = 0; j <= n - l; j++)
			ans[qry[i].second][j] = get(j, i+1);
	
	for(int i = 0; i < q; i++)
	{
		for(int j = 0; j <= n - l; j++)
			cout << ans[i][j] << " ";
		cout << "\n";
	}
	return 0;
}

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