oj.uz

Submission #822006

# Submission time Handle Problem Language Result Execution time Memory
822006 2023-08-12T00:53:25 Z NK_ Lottery (CEOI18_lot) C++17
35 / 100
 458 ms 1024 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];
	}

	// 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 : I) {
		// cout << i << nl;
		for(int x = 0; x < N - L + 1; x++) cout << ans[x][i] << " ";
		cout << nl;
	}

    return 0;
}

Subtask #1
0 / 25.0

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

Subtask #2
0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 458 ms 1004 KB Output is correct
2 Correct 409 ms 1016 KB Output is correct
3 Correct 385 ms 1016 KB Output is correct
4 Correct 379 ms 1000 KB Output is correct
5 Correct 269 ms 724 KB Output is correct
6 Correct 378 ms 980 KB Output is correct
7 Correct 263 ms 724 KB Output is correct
8 Correct 289 ms 852 KB Output is correct
9 Correct 408 ms 1024 KB Output is correct
10 Correct 385 ms 1000 KB Output is correct
11 Correct 32 ms 340 KB Output is correct
12 Correct 264 ms 828 KB Output is correct
13 Correct 309 ms 784 KB Output is correct
14 Correct 305 ms 784 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 458 ms 1004 KB Output is correct
2 Correct 409 ms 1016 KB Output is correct
3 Correct 385 ms 1016 KB Output is correct
4 Correct 379 ms 1000 KB Output is correct
5 Correct 269 ms 724 KB Output is correct
6 Correct 378 ms 980 KB Output is correct
7 Correct 263 ms 724 KB Output is correct
8 Correct 289 ms 852 KB Output is correct
9 Correct 408 ms 1024 KB Output is correct
10 Correct 385 ms 1000 KB Output is correct
11 Correct 32 ms 340 KB Output is correct
12 Correct 264 ms 828 KB Output is correct
13 Correct 309 ms 784 KB Output is correct
14 Correct 305 ms 784 KB Output is correct
15 Correct 375 ms 988 KB Output is correct
16 Correct 330 ms 952 KB Output is correct
17 Correct 376 ms 1012 KB Output is correct
18 Correct 348 ms 996 KB Output is correct
19 Correct 405 ms 1000 KB Output is correct
20 Correct 352 ms 1004 KB Output is correct
21 Correct 364 ms 1008 KB Output is correct

Subtask #5
0 / 20.0

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