답안 #617166

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
617166	2022-08-01T09:18:15 Z	usuyus	Lottery (CEOI18_lot)	C++14	100 / 100	2400 ms	8228 KB

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

int main() {
	// ios_base::sync_with_stdio(false); cin.tie(nullptr);

	int n, l; scanf("%d %d", &n, &l);
	vector<int> a(n);
	for (int &x : a) scanf("%d", &x);

	int q; scanf("%d", &q);
	vector<int> qs(q);
	for (int &x : qs) scanf("%d", &x), x = l-x;

	vector<int> qidx(q);
	iota(qidx.begin(), qidx.end(), 0);
	sort(qidx.begin(), qidx.end(), [&] (int i, int j) {
		return qs[i] < qs[j];
	});

	vector<vector<int>> ans(q, vector<int>(n-l+1));
	deque<int> sim(n+1); // offset by l -- sim[i] actually is sim[i-l]
	vector<int> cnts(l);

	for (int i=-l; i<=n-l; i++) {
		sim.pop_back();
		sim.push_front(0);

		if (0 <= i-1 && i-1 < n)
			for (int j=1; j<=n-l; j++)
				sim[j+l] -= (a[i-1] == a[j-1]);

		if (0 <= i+l-1 && i+l-1 < n)
			for (int j=-(l-1); j<n-(l-1); j++)
				sim[j+l] += (a[i + (l-1)] == a[j + (l-1)]);

		if (i >= 0) {
			for (int j=l; j<=n; j++) ++cnts[sim[j]];

			int cur = 0, cnt = n-l+1;
			for (int j : qidx) {
				for (; cur < qs[j]; cur++) cnt -= cnts[cur];
				ans[j][i] = cnt - 1;
			}

			for (int j=l; j<=n; j++) --cnts[sim[j]];
		}
	}

	for (int t=0; t<q; t++) {
		for (int i=0; i<=n-l; i++) {
			printf("%d ", ans[t][i]);
		}
		printf("\n");
	}
}

Compilation message

lot.cpp: In function 'int main()':
lot.cpp:7:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |  int n, l; scanf("%d %d", &n, &l);
      |            ~~~~~^~~~~~~~~~~~~~~~~
lot.cpp:9:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |  for (int &x : a) scanf("%d", &x);
      |                   ~~~~~^~~~~~~~~~
lot.cpp:11:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |  int q; scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~
lot.cpp:13:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  for (int &x : qs) scanf("%d", &x), x = l-x;
      |                    ~~~~~^~~~~~~~~~

Subtask #1
25.0 / 25.0

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

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	300 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	296 KB	Output is correct
6	Correct	1 ms	300 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	2 ms	212 KB	Output is correct
9	Correct	2 ms	212 KB	Output is correct
10	Correct	3 ms	340 KB	Output is correct
11	Correct	3 ms	340 KB	Output is correct
12	Correct	3 ms	212 KB	Output is correct
13	Correct	95 ms	344 KB	Output is correct
14	Correct	53 ms	460 KB	Output is correct
15	Correct	63 ms	372 KB	Output is correct
16	Correct	70 ms	468 KB	Output is correct
17	Correct	69 ms	444 KB	Output is correct
18	Correct	72 ms	444 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2205 ms	392 KB	Output is correct
2	Correct	2367 ms	392 KB	Output is correct
3	Correct	2334 ms	392 KB	Output is correct
4	Correct	2226 ms	396 KB	Output is correct
5	Correct	925 ms	396 KB	Output is correct
6	Correct	2173 ms	400 KB	Output is correct
7	Correct	1053 ms	392 KB	Output is correct
8	Correct	1425 ms	416 KB	Output is correct
9	Correct	2244 ms	392 KB	Output is correct
10	Correct	2202 ms	392 KB	Output is correct
11	Correct	106 ms	212 KB	Output is correct
12	Correct	1243 ms	388 KB	Output is correct
13	Correct	1277 ms	396 KB	Output is correct
14	Correct	1349 ms	396 KB	Output is correct

Subtask #4
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2205 ms	392 KB	Output is correct
2	Correct	2367 ms	392 KB	Output is correct
3	Correct	2334 ms	392 KB	Output is correct
4	Correct	2226 ms	396 KB	Output is correct
5	Correct	925 ms	396 KB	Output is correct
6	Correct	2173 ms	400 KB	Output is correct
7	Correct	1053 ms	392 KB	Output is correct
8	Correct	1425 ms	416 KB	Output is correct
9	Correct	2244 ms	392 KB	Output is correct
10	Correct	2202 ms	392 KB	Output is correct
11	Correct	106 ms	212 KB	Output is correct
12	Correct	1243 ms	388 KB	Output is correct
13	Correct	1277 ms	396 KB	Output is correct
14	Correct	1349 ms	396 KB	Output is correct
15	Correct	2164 ms	392 KB	Output is correct
16	Correct	1934 ms	492 KB	Output is correct
17	Correct	2300 ms	500 KB	Output is correct
18	Correct	2086 ms	500 KB	Output is correct
19	Correct	2291 ms	500 KB	Output is correct
20	Correct	2044 ms	500 KB	Output is correct
21	Correct	2044 ms	492 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	300 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	296 KB	Output is correct
6	Correct	1 ms	300 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	2 ms	212 KB	Output is correct
9	Correct	2 ms	212 KB	Output is correct
10	Correct	3 ms	340 KB	Output is correct
11	Correct	3 ms	340 KB	Output is correct
12	Correct	3 ms	212 KB	Output is correct
13	Correct	95 ms	344 KB	Output is correct
14	Correct	53 ms	460 KB	Output is correct
15	Correct	63 ms	372 KB	Output is correct
16	Correct	70 ms	468 KB	Output is correct
17	Correct	69 ms	444 KB	Output is correct
18	Correct	72 ms	444 KB	Output is correct
19	Correct	2205 ms	392 KB	Output is correct
20	Correct	2367 ms	392 KB	Output is correct
21	Correct	2334 ms	392 KB	Output is correct
22	Correct	2226 ms	396 KB	Output is correct
23	Correct	925 ms	396 KB	Output is correct
24	Correct	2173 ms	400 KB	Output is correct
25	Correct	1053 ms	392 KB	Output is correct
26	Correct	1425 ms	416 KB	Output is correct
27	Correct	2244 ms	392 KB	Output is correct
28	Correct	2202 ms	392 KB	Output is correct
29	Correct	106 ms	212 KB	Output is correct
30	Correct	1243 ms	388 KB	Output is correct
31	Correct	1277 ms	396 KB	Output is correct
32	Correct	1349 ms	396 KB	Output is correct
33	Correct	2164 ms	392 KB	Output is correct
34	Correct	1934 ms	492 KB	Output is correct
35	Correct	2300 ms	500 KB	Output is correct
36	Correct	2086 ms	500 KB	Output is correct
37	Correct	2291 ms	500 KB	Output is correct
38	Correct	2044 ms	500 KB	Output is correct
39	Correct	2044 ms	492 KB	Output is correct
40	Correct	2194 ms	1924 KB	Output is correct
41	Correct	680 ms	572 KB	Output is correct
42	Correct	2397 ms	1932 KB	Output is correct
43	Correct	2080 ms	1592 KB	Output is correct
44	Correct	2043 ms	1724 KB	Output is correct
45	Correct	2400 ms	8096 KB	Output is correct
46	Correct	662 ms	1156 KB	Output is correct
47	Correct	2035 ms	8228 KB	Output is correct
48	Correct	1970 ms	6256 KB	Output is correct
49	Correct	2388 ms	6892 KB	Output is correct

답안 #617166

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