oj.uz

답안 #821999

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
821999 2023-08-12T00:45:39 Z NK_ Lottery (CEOI18_lot) C++17
35 / 100
 472 ms 1116 KB 
// 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);
			++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];
	}

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

    return 0;
}

Subtask #1
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 324 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 324 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 472 ms 1032 KB Output is correct
2 Correct 408 ms 1032 KB Output is correct
3 Correct 389 ms 1032 KB Output is correct
4 Correct 366 ms 1108 KB Output is correct
5 Correct 287 ms 828 KB Output is correct
6 Correct 371 ms 1068 KB Output is correct
7 Correct 288 ms 824 KB Output is correct
8 Correct 303 ms 944 KB Output is correct
9 Correct 381 ms 1088 KB Output is correct
10 Correct 388 ms 1048 KB Output is correct
11 Correct 25 ms 468 KB Output is correct
12 Correct 265 ms 920 KB Output is correct
13 Correct 294 ms 884 KB Output is correct
14 Correct 290 ms 900 KB Output is correct

Subtask #4
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 472 ms 1032 KB Output is correct
2 Correct 408 ms 1032 KB Output is correct
3 Correct 389 ms 1032 KB Output is correct
4 Correct 366 ms 1108 KB Output is correct
5 Correct 287 ms 828 KB Output is correct
6 Correct 371 ms 1068 KB Output is correct
7 Correct 288 ms 824 KB Output is correct
8 Correct 303 ms 944 KB Output is correct
9 Correct 381 ms 1088 KB Output is correct
10 Correct 388 ms 1048 KB Output is correct
11 Correct 25 ms 468 KB Output is correct
12 Correct 265 ms 920 KB Output is correct
13 Correct 294 ms 884 KB Output is correct
14 Correct 290 ms 900 KB Output is correct
15 Correct 380 ms 1016 KB Output is correct
16 Correct 330 ms 1080 KB Output is correct
17 Correct 382 ms 1116 KB Output is correct
18 Correct 379 ms 1108 KB Output is correct
19 Correct 387 ms 1100 KB Output is correct
20 Correct 384 ms 1108 KB Output is correct
21 Correct 382 ms 1116 KB Output is correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 324 KB Output isn't correct
3 Halted 0 ms 0 KB -