답안 #99625 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
99625	2019-03-05T20:12:22 Z	Anai	Lottery (CEOI18_lot)	C++14	100 / 100	553 ms	8440 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 = 2; 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
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	512 KB	Output is correct
3	Correct	2 ms	512 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	2 ms	512 KB	Output is correct
7	Correct	3 ms	512 KB	Output is correct
8	Correct	3 ms	512 KB	Output is correct
9	Correct	3 ms	512 KB	Output is correct
10	Correct	3 ms	512 KB	Output is correct
11	Correct	3 ms	512 KB	Output is correct
12	Correct	3 ms	512 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	512 KB	Output is correct
3	Correct	2 ms	512 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	2 ms	512 KB	Output is correct
7	Correct	3 ms	512 KB	Output is correct
8	Correct	3 ms	512 KB	Output is correct
9	Correct	3 ms	512 KB	Output is correct
10	Correct	3 ms	512 KB	Output is correct
11	Correct	3 ms	512 KB	Output is correct
12	Correct	3 ms	512 KB	Output is correct
13	Correct	20 ms	512 KB	Output is correct
14	Correct	17 ms	640 KB	Output is correct
15	Correct	22 ms	612 KB	Output is correct
16	Correct	19 ms	768 KB	Output is correct
17	Correct	18 ms	768 KB	Output is correct
18	Correct	24 ms	760 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	391 ms	632 KB	Output is correct
2	Correct	408 ms	640 KB	Output is correct
3	Correct	387 ms	604 KB	Output is correct
4	Correct	400 ms	732 KB	Output is correct
5	Correct	264 ms	760 KB	Output is correct
6	Correct	356 ms	640 KB	Output is correct
7	Correct	239 ms	640 KB	Output is correct
8	Correct	317 ms	760 KB	Output is correct
9	Correct	369 ms	680 KB	Output is correct
10	Correct	362 ms	640 KB	Output is correct
11	Correct	29 ms	512 KB	Output is correct
12	Correct	269 ms	640 KB	Output is correct
13	Correct	303 ms	632 KB	Output is correct
14	Correct	281 ms	760 KB	Output is correct

Subtask #4
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	391 ms	632 KB	Output is correct
2	Correct	408 ms	640 KB	Output is correct
3	Correct	387 ms	604 KB	Output is correct
4	Correct	400 ms	732 KB	Output is correct
5	Correct	264 ms	760 KB	Output is correct
6	Correct	356 ms	640 KB	Output is correct
7	Correct	239 ms	640 KB	Output is correct
8	Correct	317 ms	760 KB	Output is correct
9	Correct	369 ms	680 KB	Output is correct
10	Correct	362 ms	640 KB	Output is correct
11	Correct	29 ms	512 KB	Output is correct
12	Correct	269 ms	640 KB	Output is correct
13	Correct	303 ms	632 KB	Output is correct
14	Correct	281 ms	760 KB	Output is correct
15	Correct	539 ms	644 KB	Output is correct
16	Correct	365 ms	764 KB	Output is correct
17	Correct	371 ms	640 KB	Output is correct
18	Correct	370 ms	640 KB	Output is correct
19	Correct	364 ms	760 KB	Output is correct
20	Correct	372 ms	716 KB	Output is correct
21	Correct	367 ms	716 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	512 KB	Output is correct
3	Correct	2 ms	512 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	2 ms	512 KB	Output is correct
7	Correct	3 ms	512 KB	Output is correct
8	Correct	3 ms	512 KB	Output is correct
9	Correct	3 ms	512 KB	Output is correct
10	Correct	3 ms	512 KB	Output is correct
11	Correct	3 ms	512 KB	Output is correct
12	Correct	3 ms	512 KB	Output is correct
13	Correct	20 ms	512 KB	Output is correct
14	Correct	17 ms	640 KB	Output is correct
15	Correct	22 ms	612 KB	Output is correct
16	Correct	19 ms	768 KB	Output is correct
17	Correct	18 ms	768 KB	Output is correct
18	Correct	24 ms	760 KB	Output is correct
19	Correct	391 ms	632 KB	Output is correct
20	Correct	408 ms	640 KB	Output is correct
21	Correct	387 ms	604 KB	Output is correct
22	Correct	400 ms	732 KB	Output is correct
23	Correct	264 ms	760 KB	Output is correct
24	Correct	356 ms	640 KB	Output is correct
25	Correct	239 ms	640 KB	Output is correct
26	Correct	317 ms	760 KB	Output is correct
27	Correct	369 ms	680 KB	Output is correct
28	Correct	362 ms	640 KB	Output is correct
29	Correct	29 ms	512 KB	Output is correct
30	Correct	269 ms	640 KB	Output is correct
31	Correct	303 ms	632 KB	Output is correct
32	Correct	281 ms	760 KB	Output is correct
33	Correct	539 ms	644 KB	Output is correct
34	Correct	365 ms	764 KB	Output is correct
35	Correct	371 ms	640 KB	Output is correct
36	Correct	370 ms	640 KB	Output is correct
37	Correct	364 ms	760 KB	Output is correct
38	Correct	372 ms	716 KB	Output is correct
39	Correct	367 ms	716 KB	Output is correct
40	Correct	399 ms	2068 KB	Output is correct
41	Correct	183 ms	780 KB	Output is correct
42	Correct	399 ms	2296 KB	Output is correct
43	Correct	380 ms	1912 KB	Output is correct
44	Correct	404 ms	1944 KB	Output is correct
45	Correct	553 ms	8216 KB	Output is correct
46	Correct	214 ms	1656 KB	Output is correct
47	Correct	455 ms	8440 KB	Output is correct
48	Correct	425 ms	6564 KB	Output is correct
49	Correct	466 ms	7132 KB	Output is correct

답안 #99625

Compilation message

Subtask #1 25.0 / 25.0

Subtask #2 20.0 / 20.0

Subtask #3 20.0 / 20.0

Subtask #4 15.0 / 15.0

Subtask #5 20.0 / 20.0

Subtask #1
25.0 / 25.0

Subtask #2
20.0 / 20.0

Subtask #3
20.0 / 20.0

Subtask #4
15.0 / 15.0

Subtask #5
20.0 / 20.0