Submission #99624

#	Time	Username	Problem	Language	Result	Execution time	Memory
99624		Anai	Lottery (CEOI18_lot)	C++14	0 / 100	413 ms	576 KiB

lot

#include <bits/stdc++.h>
using namespace std;

const int N = 10000, Q = 101;

int v[2 * N], map_q[N], ant[Q][N];

map<int, int> mq;
vector<int> qs;
int n, l, q;

int main() {
#ifdef HOME
	freopen("lot.in", "r", stdin);
	freopen("lot.out", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int tmp = 0;

	cin >> n >> l;
	for (int i = 0; i < n; ++i) {
		cin >> v[i];
		v[i + n] = v[i]; } 

	cin >> q;
	qs.resize(q);
	for (int i = 0; i < q; ++i) {
		cin >> qs[i];
		mq[qs[i]] = 0; }

	for (auto &i: mq) {
		i.second = ++tmp;
		map_q[i.first] = tmp; }

	for (int i = N - 2; i >= 0; --i)
		if (!map_q[i])
			map_q[i] = map_q[i + 1];

	for (int shift = 1; shift < n; ++shift) {
		int dif = 0, st = shift, dr = shift;

		for (int i = 0; i < l; ++i) {
			dif+= int(v[dr] != v[i]);
			dr = (dr + 1 == n ? 0 : dr + 1); }
		if (st <= (dr == 0 ? n - 1 : dr - 1))
			ant[map_q[dif]][0]+= 1;

		for (int i = 1; i < n - l + 1; ++i) {
			dif-= int(v[st] != v[i - 1]);
			st = (st + 1 == n ? 0 : st + 1);
			dif+= int(v[dr] != v[i + l - 1]);
			dr = (dr + 1 == n ? 0 : dr + 1);
			if (st <= (dr == 0 ? n - 1 : dr - 1))
				ant[map_q[dif]][i]+= 1; } }

	for (int i = 1; i <= q; ++i)
		for (int j = 0; j < n - l + 1; ++j)
			ant[i][j]+= ant[i - 1][j];

	for (int i = 0; i < q; ++i) {
		for (int j = 0; j < n - l + 1; ++j)
			cout << ant[map_q[qs[i]]][j] << ' ' ;
		cout << '\n'; }

	return 0; }

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