oj.uz

Submission #311771

# Submission time Handle Problem Language Result Execution time Memory
311771 2020-10-11T14:27:05 Z shivensinha4 Lottery (CEOI18_lot) C++17
100 / 100
 1441 ms 8312 KB 
#include <bits/stdc++.h> 
using namespace std; 
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'

const int MXN = 1e4, MXQ = 100;
int freq[MXQ+1][MXN+2];

int main() {
	#ifdef shiven
	freopen("test.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, l; cin >> n >> l;
	vi nums(n);
	for_(i, 0, n) cin >> nums[i];
	int q; cin >> q;
	vector<ii> qrs(q);
	vi qrsv(q);
	for_(i, 0, q) {
		cin >> qrs[i].first;
		qrsv[i] = qrs[i].first;
		qrs[i].second = i;
	}
	
	sort(qrs.begin(), qrs.end());
	sort(qrsv.begin(), qrsv.end());
	
	for_(d, 1, n+1) {
		vi temp(n);
		for_(j, d, n) if (nums[j] != nums[j-d]) temp[j] += 1;
		for_(i, d, n) temp[i] += temp[i-1];
		for_(j, d, n-l+1) {
			int dist = temp[j+l-1] - (j > 0 ? temp[j-1] : 0);
			int idx = lower_bound(qrsv.begin(), qrsv.end(), dist) - qrsv.begin();
			if (idx < q) {
				freq[qrs[idx].second][j] += 1; freq[qrs[idx].second][j-d] += 1;
			}
		}
	}
	
	for_(i, 0, q) for_(j, 0, n-l+1) if (i > 0) freq[qrs[i].second][j] += freq[qrs[i-1].second][j];
	
	for_(i, 0, q) {
		for_(j, 0, n-l+1) cout << freq[i][j] << " ";
		cout << endl;
	}

	return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 416 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1 ms 512 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 416 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 31 ms 384 KB Output is correct
14 Correct 19 ms 640 KB Output is correct
15 Correct 20 ms 512 KB Output is correct
16 Correct 26 ms 632 KB Output is correct
17 Correct 21 ms 640 KB Output is correct
18 Correct 20 ms 640 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 701 ms 632 KB Output is correct
2 Correct 602 ms 632 KB Output is correct
3 Correct 397 ms 512 KB Output is correct
4 Correct 333 ms 504 KB Output is correct
5 Correct 272 ms 504 KB Output is correct
6 Correct 323 ms 508 KB Output is correct
7 Correct 352 ms 508 KB Output is correct
8 Correct 433 ms 504 KB Output is correct
9 Correct 340 ms 504 KB Output is correct
10 Correct 348 ms 632 KB Output is correct
11 Correct 30 ms 384 KB Output is correct
12 Correct 257 ms 456 KB Output is correct
13 Correct 282 ms 504 KB Output is correct
14 Correct 289 ms 504 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 701 ms 632 KB Output is correct
2 Correct 602 ms 632 KB Output is correct
3 Correct 397 ms 512 KB Output is correct
4 Correct 333 ms 504 KB Output is correct
5 Correct 272 ms 504 KB Output is correct
6 Correct 323 ms 508 KB Output is correct
7 Correct 352 ms 508 KB Output is correct
8 Correct 433 ms 504 KB Output is correct
9 Correct 340 ms 504 KB Output is correct
10 Correct 348 ms 632 KB Output is correct
11 Correct 30 ms 384 KB Output is correct
12 Correct 257 ms 456 KB Output is correct
13 Correct 282 ms 504 KB Output is correct
14 Correct 289 ms 504 KB Output is correct
15 Correct 534 ms 512 KB Output is correct
16 Correct 323 ms 504 KB Output is correct
17 Correct 362 ms 632 KB Output is correct
18 Correct 332 ms 504 KB Output is correct
19 Correct 334 ms 504 KB Output is correct
20 Correct 365 ms 632 KB Output is correct
21 Correct 335 ms 504 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 416 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1 ms 512 KB Output is correct
13 Correct 31 ms 384 KB Output is correct
14 Correct 19 ms 640 KB Output is correct
15 Correct 20 ms 512 KB Output is correct
16 Correct 26 ms 632 KB Output is correct
17 Correct 21 ms 640 KB Output is correct
18 Correct 20 ms 640 KB Output is correct
19 Correct 701 ms 632 KB Output is correct
20 Correct 602 ms 632 KB Output is correct
21 Correct 397 ms 512 KB Output is correct
22 Correct 333 ms 504 KB Output is correct
23 Correct 272 ms 504 KB Output is correct
24 Correct 323 ms 508 KB Output is correct
25 Correct 352 ms 508 KB Output is correct
26 Correct 433 ms 504 KB Output is correct
27 Correct 340 ms 504 KB Output is correct
28 Correct 348 ms 632 KB Output is correct
29 Correct 30 ms 384 KB Output is correct
30 Correct 257 ms 456 KB Output is correct
31 Correct 282 ms 504 KB Output is correct
32 Correct 289 ms 504 KB Output is correct
33 Correct 534 ms 512 KB Output is correct
34 Correct 323 ms 504 KB Output is correct
35 Correct 362 ms 632 KB Output is correct
36 Correct 332 ms 504 KB Output is correct
37 Correct 334 ms 504 KB Output is correct
38 Correct 365 ms 632 KB Output is correct
39 Correct 335 ms 504 KB Output is correct
40 Correct 989 ms 1992 KB Output is correct
41 Correct 242 ms 632 KB Output is correct
42 Correct 515 ms 2040 KB Output is correct
43 Correct 467 ms 1656 KB Output is correct
44 Correct 475 ms 1784 KB Output is correct
45 Correct 1441 ms 8172 KB Output is correct
46 Correct 251 ms 1528 KB Output is correct
47 Correct 828 ms 8312 KB Output is correct
48 Correct 622 ms 6452 KB Output is correct
49 Correct 624 ms 7160 KB Output is correct