oj.uz

Submission #754279

# Submission time Handle Problem Language Result Execution time Memory
754279 2023-06-07T11:49:33 Z MetalPower Lottery (CEOI18_lot) C++14
35 / 100
 648 ms 4600 KB 
#include <bits/stdc++.h>
using namespace std;

const int MX = 1e4 + 10;

int N, L, Q, arr[MX], que[MX], pref[MX], ans[MX][105];
vector<int> sq;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N >> L;
	for(int i = 0; i < N; i++) cin >> arr[i];

	cin >> Q;
	for(int i = 0; i < Q; i++){
		cin >> que[i];
		sq.push_back(que[i]);
	}

	sort(sq.begin(), sq.end());

	for(int df = 1; df < N - L + 1; df++){
		for(int i = 0; i < N - df; i++){
			if(arr[i] != arr[i + df]) pref[i + 1] = pref[i] + 1;
			else pref[i + 1] = pref[i]; 
		}
		for(int i = 0; i < N - L + 1 - df; i++){
			int curr = pref[i + L] - pref[i], id = lower_bound(sq.begin(), sq.end(), curr) - sq.begin();
			ans[i][id]++;
			ans[i + df][id]++;
		}
	}

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

	for(int i = 0; i < Q; i++){
		int id = lower_bound(sq.begin(), sq.end(), que[i]) - sq.begin();
		for(int k = 0; k < N - L + 1; k++) cout << ans[k][i] << " ";
		cout << '\n';
	}
}

Compilation message

lot.cpp: In function 'int main()':
lot.cpp:40:7: warning: unused variable 'id' [-Wunused-variable]
   40 |   int id = lower_bound(sq.begin(), sq.end(), que[i]) - sq.begin();
      |       ^~

Subtask #1
0 / 25.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 340 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 648 ms 4516 KB Output is correct
2 Correct 501 ms 4516 KB Output is correct
3 Correct 354 ms 4516 KB Output is correct
4 Correct 344 ms 4512 KB Output is correct
5 Correct 168 ms 2516 KB Output is correct
6 Correct 331 ms 4312 KB Output is correct
7 Correct 137 ms 2564 KB Output is correct
8 Correct 233 ms 3384 KB Output is correct
9 Correct 355 ms 4456 KB Output is correct
10 Correct 348 ms 4524 KB Output is correct
11 Correct 23 ms 1180 KB Output is correct
12 Correct 235 ms 3336 KB Output is correct
13 Correct 184 ms 2920 KB Output is correct
14 Correct 198 ms 2928 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 648 ms 4516 KB Output is correct
2 Correct 501 ms 4516 KB Output is correct
3 Correct 354 ms 4516 KB Output is correct
4 Correct 344 ms 4512 KB Output is correct
5 Correct 168 ms 2516 KB Output is correct
6 Correct 331 ms 4312 KB Output is correct
7 Correct 137 ms 2564 KB Output is correct
8 Correct 233 ms 3384 KB Output is correct
9 Correct 355 ms 4456 KB Output is correct
10 Correct 348 ms 4524 KB Output is correct
11 Correct 23 ms 1180 KB Output is correct
12 Correct 235 ms 3336 KB Output is correct
13 Correct 184 ms 2920 KB Output is correct
14 Correct 198 ms 2928 KB Output is correct
15 Correct 372 ms 4380 KB Output is correct
16 Correct 310 ms 4196 KB Output is correct
17 Correct 384 ms 4600 KB Output is correct
18 Correct 363 ms 4568 KB Output is correct
19 Correct 374 ms 4564 KB Output is correct
20 Correct 359 ms 4564 KB Output is correct
21 Correct 410 ms 4564 KB Output is correct

Subtask #5
0 / 20.0

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