답안 #94424 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
94424	2019-01-18T11:26:44 Z	Noam527	Lottery (CEOI18_lot)	C++17	100 / 100	599 ms	8188 KB

#include <bits/stdc++.h>
#include <unordered_set>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7, inf = 1e9 + 7;
using namespace std;

void debug(string names) {
	cout << '\n';
}
template<typename A1, typename... A2>
void debug(string names, A1 par, A2... left) {
	int pos = 0;
	for (; pos < names.size() && names[pos] != ' '  && names[pos] != ','; pos++)
		cout << names[pos];
	cout << ": " << par << "  ";
	while (pos < names.size() && (names[pos] == ' ' || names[pos] == ',')) {
		pos++;
	}
	names.erase(names.begin(), names.begin() + pos);
	debug(names, left...);
}

int n, l, q;
vector<int> a;
vector<pair<int, int>> k;
vector<int> to;
int ans[101][10001] = {};



int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> l;
	a.resize(n);
	for (auto &i : a) cin >> i;
	cin >> q;
	k.resize(q);
	for (int i = 0; i < q; i++) cin >> k[i].first, k[i].second = i;
	sort(k.begin(), k.end());
	to.resize(l + 1);
	to[l] = q;
	int nxt = q - 1;
	while (nxt >= 0 && l == k[nxt].first) to[l]--, nxt--;
	for (int i = l - 1; i >= 0; i--) {
		to[i] = to[i + 1];
		while (nxt >= 0 && i == k[nxt].first) to[i]--, nxt--;
	}
//	cout << "to: ";
//	for (const auto &i : to) cout << i << " "; cout << '\n';

	int dist;
	for (int d = 1; d + l - 1 < n; d++) {
		dist = 0;
		for (int i = 0; i < l; i++)
			if (a[i] != a[i + d]) dist++;
		ans[to[dist]][0]++;
		ans[to[dist]][d]++;
		for (int i = 1; i + d + l - 1 < n; i++) {
			if (a[i - 1] != a[i + d - 1]) dist--;
			if (a[i + l - 1] != a[i + d + l - 1]) dist++;
			ans[to[dist]][i]++;
			ans[to[dist]][i + d]++;
		}
	}
	for (int i = 1; i < q; i++) for (int j = 0; j < n; j++) ans[i][j] += ans[i - 1][j];
	for (int i = 0; i < q; i++) k[i].first = i, swap(k[i].first, k[i].second);
	sort(k.begin(), k.end());
	for (auto &i : k) {
		for (int j = 0; j < n - l + 1; j++)
			cout << ans[i.second][j] << " ";
		cout << '\n';
	}
}

Subtask #1
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	504 KB	Output is correct
4	Correct	2 ms	248 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	548 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	508 KB	Output is correct
12	Correct	3 ms	504 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	504 KB	Output is correct
4	Correct	2 ms	248 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	548 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	508 KB	Output is correct
12	Correct	3 ms	504 KB	Output is correct
13	Correct	10 ms	504 KB	Output is correct
14	Correct	7 ms	632 KB	Output is correct
15	Correct	6 ms	504 KB	Output is correct
16	Correct	10 ms	732 KB	Output is correct
17	Correct	8 ms	632 KB	Output is correct
18	Correct	9 ms	696 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	352 ms	528 KB	Output is correct
2	Correct	516 ms	548 KB	Output is correct
3	Correct	198 ms	632 KB	Output is correct
4	Correct	148 ms	632 KB	Output is correct
5	Correct	56 ms	532 KB	Output is correct
6	Correct	135 ms	576 KB	Output is correct
7	Correct	54 ms	632 KB	Output is correct
8	Correct	82 ms	504 KB	Output is correct
9	Correct	146 ms	600 KB	Output is correct
10	Correct	145 ms	632 KB	Output is correct
11	Correct	13 ms	376 KB	Output is correct
12	Correct	94 ms	632 KB	Output is correct
13	Correct	73 ms	504 KB	Output is correct
14	Correct	89 ms	504 KB	Output is correct

Subtask #4
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	352 ms	528 KB	Output is correct
2	Correct	516 ms	548 KB	Output is correct
3	Correct	198 ms	632 KB	Output is correct
4	Correct	148 ms	632 KB	Output is correct
5	Correct	56 ms	532 KB	Output is correct
6	Correct	135 ms	576 KB	Output is correct
7	Correct	54 ms	632 KB	Output is correct
8	Correct	82 ms	504 KB	Output is correct
9	Correct	146 ms	600 KB	Output is correct
10	Correct	145 ms	632 KB	Output is correct
11	Correct	13 ms	376 KB	Output is correct
12	Correct	94 ms	632 KB	Output is correct
13	Correct	73 ms	504 KB	Output is correct
14	Correct	89 ms	504 KB	Output is correct
15	Correct	226 ms	556 KB	Output is correct
16	Correct	128 ms	628 KB	Output is correct
17	Correct	168 ms	560 KB	Output is correct
18	Correct	150 ms	616 KB	Output is correct
19	Correct	149 ms	760 KB	Output is correct
20	Correct	150 ms	632 KB	Output is correct
21	Correct	150 ms	632 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	504 KB	Output is correct
4	Correct	2 ms	248 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	548 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	508 KB	Output is correct
12	Correct	3 ms	504 KB	Output is correct
13	Correct	10 ms	504 KB	Output is correct
14	Correct	7 ms	632 KB	Output is correct
15	Correct	6 ms	504 KB	Output is correct
16	Correct	10 ms	732 KB	Output is correct
17	Correct	8 ms	632 KB	Output is correct
18	Correct	9 ms	696 KB	Output is correct
19	Correct	352 ms	528 KB	Output is correct
20	Correct	516 ms	548 KB	Output is correct
21	Correct	198 ms	632 KB	Output is correct
22	Correct	148 ms	632 KB	Output is correct
23	Correct	56 ms	532 KB	Output is correct
24	Correct	135 ms	576 KB	Output is correct
25	Correct	54 ms	632 KB	Output is correct
26	Correct	82 ms	504 KB	Output is correct
27	Correct	146 ms	600 KB	Output is correct
28	Correct	145 ms	632 KB	Output is correct
29	Correct	13 ms	376 KB	Output is correct
30	Correct	94 ms	632 KB	Output is correct
31	Correct	73 ms	504 KB	Output is correct
32	Correct	89 ms	504 KB	Output is correct
33	Correct	226 ms	556 KB	Output is correct
34	Correct	128 ms	628 KB	Output is correct
35	Correct	168 ms	560 KB	Output is correct
36	Correct	150 ms	616 KB	Output is correct
37	Correct	149 ms	760 KB	Output is correct
38	Correct	150 ms	632 KB	Output is correct
39	Correct	150 ms	632 KB	Output is correct
40	Correct	544 ms	1992 KB	Output is correct
41	Correct	12 ms	1400 KB	Output is correct
42	Correct	162 ms	2012 KB	Output is correct
43	Correct	151 ms	1784 KB	Output is correct
44	Correct	154 ms	1912 KB	Output is correct
45	Correct	599 ms	8056 KB	Output is correct
46	Correct	19 ms	4728 KB	Output is correct
47	Correct	218 ms	8188 KB	Output is correct
48	Correct	199 ms	6520 KB	Output is correct
49	Correct	202 ms	7160 KB	Output is correct

답안 #94424

Compilation message

Subtask #1 25.0 / 25.0

Subtask #2 20.0 / 20.0

Subtask #3 20.0 / 20.0

Subtask #4 15.0 / 15.0

Subtask #5 20.0 / 20.0

Subtask #1
25.0 / 25.0

Subtask #2
20.0 / 20.0

Subtask #3
20.0 / 20.0

Subtask #4
15.0 / 15.0

Subtask #5
20.0 / 20.0