답안 #822008

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
822008	2023-08-12T00:54:17 Z	NK_	Lottery (CEOI18_lot)	C++17	100 / 100	1006 ms	8712 KB

lot

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

template<class T> using V = vector<T>;
using vi = V<int>;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, L; cin >> N >> L;
	vi A(N); for(auto& x : A) cin >> x;

	int Q; cin >> Q;
	vi K(Q); for(auto& x : K) cin >> x;

	vi I(Q); iota(begin(I), end(I), 0); sort(begin(I), end(I), [&](int x, int y) {
		return K[x] < K[y];
	});

	sort(begin(K), end(K));

	V<vi> ans(N - L + 1, vi(Q));

	vi P;
	for(int d = 1; d <= N; d++) {
		P = {0};
		for(int i = 0; i < N - d; i++) {
			P.push_back(P.back() + (A[i] != A[i + d]));
		}

		auto query = [&](int l, int r) {
			return P[r + 1] - P[l];
		};

		for(int i = 0; i < N; i++) {
			int j = i + d;
			if (j + L - 1 >= N) continue;

			int k = query(i, i + L - 1);
			int ki = lower_bound(begin(K), end(K), k) - begin(K);
			if (ki < Q) {
				++ans[i][ki]; 
				++ans[i + d][ki];
			}
		}
	}

	for(int i = 0; i < N - L + 1; i++) {
		for(int x = 1; x < Q; x++) ans[i][x] += ans[i][x-1];
	}

	vi ord(Q); for(int i = 0; i < Q; i++) ord[I[i]] = i;

	// for(auto x : I) cout << x << " ";
	// cout << nl;

	// for(auto x : ord) cout << x << " ";
	// cout << nl;
	
	for(auto i : ord) {
		// cout << i << nl;
		for(int x = 0; x < N - L + 1; x++) cout << ans[x][i] << " ";
		cout << nl;
	}

    return 0;
}

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	340 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	2 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 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	340 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	2 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	25 ms	460 KB	Output is correct
14	Correct	17 ms	516 KB	Output is correct
15	Correct	16 ms	528 KB	Output is correct
16	Correct	19 ms	600 KB	Output is correct
17	Correct	17 ms	556 KB	Output is correct
18	Correct	20 ms	552 KB	Output is correct

Subtask #3

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	416 ms	1008 KB	Output is correct
2	Correct	341 ms	1008 KB	Output is correct
3	Correct	374 ms	1016 KB	Output is correct
4	Correct	330 ms	1000 KB	Output is correct
5	Correct	253 ms	724 KB	Output is correct
6	Correct	359 ms	1000 KB	Output is correct
7	Correct	269 ms	724 KB	Output is correct
8	Correct	310 ms	852 KB	Output is correct
9	Correct	337 ms	988 KB	Output is correct
10	Correct	329 ms	996 KB	Output is correct
11	Correct	30 ms	468 KB	Output is correct
12	Correct	248 ms	852 KB	Output is correct
13	Correct	281 ms	788 KB	Output is correct
14	Correct	282 ms	784 KB	Output is correct

Subtask #4

15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	416 ms	1008 KB	Output is correct
2	Correct	341 ms	1008 KB	Output is correct
3	Correct	374 ms	1016 KB	Output is correct
4	Correct	330 ms	1000 KB	Output is correct
5	Correct	253 ms	724 KB	Output is correct
6	Correct	359 ms	1000 KB	Output is correct
7	Correct	269 ms	724 KB	Output is correct
8	Correct	310 ms	852 KB	Output is correct
9	Correct	337 ms	988 KB	Output is correct
10	Correct	329 ms	996 KB	Output is correct
11	Correct	30 ms	468 KB	Output is correct
12	Correct	248 ms	852 KB	Output is correct
13	Correct	281 ms	788 KB	Output is correct
14	Correct	282 ms	784 KB	Output is correct
15	Correct	335 ms	984 KB	Output is correct
16	Correct	340 ms	952 KB	Output is correct
17	Correct	345 ms	1008 KB	Output is correct
18	Correct	321 ms	996 KB	Output is correct
19	Correct	329 ms	980 KB	Output is correct
20	Correct	333 ms	1000 KB	Output is correct
21	Correct	388 ms	1012 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	340 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	2 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	25 ms	460 KB	Output is correct
14	Correct	17 ms	516 KB	Output is correct
15	Correct	16 ms	528 KB	Output is correct
16	Correct	19 ms	600 KB	Output is correct
17	Correct	17 ms	556 KB	Output is correct
18	Correct	20 ms	552 KB	Output is correct
19	Correct	416 ms	1008 KB	Output is correct
20	Correct	341 ms	1008 KB	Output is correct
21	Correct	374 ms	1016 KB	Output is correct
22	Correct	330 ms	1000 KB	Output is correct
23	Correct	253 ms	724 KB	Output is correct
24	Correct	359 ms	1000 KB	Output is correct
25	Correct	269 ms	724 KB	Output is correct
26	Correct	310 ms	852 KB	Output is correct
27	Correct	337 ms	988 KB	Output is correct
28	Correct	329 ms	996 KB	Output is correct
29	Correct	30 ms	468 KB	Output is correct
30	Correct	248 ms	852 KB	Output is correct
31	Correct	281 ms	788 KB	Output is correct
32	Correct	282 ms	784 KB	Output is correct
33	Correct	335 ms	984 KB	Output is correct
34	Correct	340 ms	952 KB	Output is correct
35	Correct	345 ms	1008 KB	Output is correct
36	Correct	321 ms	996 KB	Output is correct
37	Correct	329 ms	980 KB	Output is correct
38	Correct	333 ms	1000 KB	Output is correct
39	Correct	388 ms	1012 KB	Output is correct
40	Correct	642 ms	2408 KB	Output is correct
41	Correct	231 ms	676 KB	Output is correct
42	Correct	456 ms	2436 KB	Output is correct
43	Correct	424 ms	2072 KB	Output is correct
44	Correct	466 ms	2200 KB	Output is correct
45	Correct	1006 ms	8584 KB	Output is correct
46	Correct	244 ms	1236 KB	Output is correct
47	Correct	691 ms	8712 KB	Output is correct
48	Correct	567 ms	6732 KB	Output is correct
49	Correct	558 ms	7376 KB	Output is correct