oj.uz

Submission #99624

# Submission time Handle Problem Language Result Execution time Memory
99624 2019-03-05T20:00:20 Z Anai Lottery (CEOI18_lot) C++14
0 / 100
 413 ms 576 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 413 ms 576 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 413 ms 576 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -