Submission #77981

#	Time	Username	Problem	Language	Result	Execution time	Memory
77981		aminra	Lottery (CEOI18_lot)	C++14	100 / 100	1576 ms	9256 KiB

lot

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MOD = (int)1e9 + 7;
const int MAXN = (int)1e4 + 3;
const int MAXS = (int)107;
const int infint = (int)1e9;
const ll inf = (ll)1e18;
int a[MAXN], n, cur[MAXN], q, ans[MAXS][MAXN], perm[MAXN], l;
struct query{
	int val, idx;
} Q[MAXS];
bool cmp(query a, query b)
{
	return a.val < b.val;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> l;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	cin >> q;
	for (int i = 0; i < q; i++)
	{
		cin >> Q[i].val;
		Q[i].idx = i;
	}
	sort(Q, Q + q, cmp);
	vector<int> v;
	for (int i = 0; i < q; i++)
		v.push_back(Q[i].val);
	
	for (int i = 0; i < q; i++)
		for (int j = 0; j < n; j++)
			ans[i][j] = 0;
	
	for (int i = 1; i < n; i++)
	{
		memset(cur, 0, sizeof cur);
		for (int j = 0; j + i < n; j++)
			if(a[i + j] != a[j])
			{
				cur[j]++;
				if(j >= l)
					cur[j - l]--;
			}
		for (int j = n - i - 1; j >= 0; j--)
			cur[j] += cur[j + 1];
		for (int j = 0; j + i <= n - l; j++)
		{
			//dist[j][i + j] = cur[j]
			int idx = lower_bound(v.begin(), v.end(), cur[j]) - v.begin() - 1;
			if(idx == -1)
				continue;
			ans[idx][j]++, ans[idx][i + j]++;
		}
	}
	for (int i = q - 1; i >= 0; i--)
		for (int j = 0; j < n; j++)
			ans[i][j] += ans[i + 1][j];
	for (int i = 0; i < q; i++)
		perm[Q[i].idx] = i;
	for (int i = 0; i < q; i++)
	{
		for (int j = 0; j < n - l + 1; j++)
			cout << n - l - ans[perm[i]][j] << " ";
		cout << "\n";
	}
}

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