# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
116442 |
2019-06-12T13:04:23 Z |
maruii |
Lottery (CEOI18_lot) |
C++14 |
|
252 ms |
1144 KB |
#include <bits/stdc++.h>
using namespace std;
int A[100001], ans[100][100001], idx[100];
int X[100001], B[100001];
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int N, L; cin >> N >> L;
for (int i = 1; i <= N; ++i) cin >> A[i];
int Q; cin >> Q;
pair<int, int> qry[Q];
for (int i = 0; i < Q; ++i) {
int x; cin >> x;
qry[i] = {x, i};
}
sort(qry, qry + Q);
memset(B, -1, sizeof(B));
for (int i = 0; i < Q; ++i) {
B[qry[i].first] = i;
idx[qry[i].second] = i;
}
for (int i = L; i; --i)
if (B[i-1] == -1) B[i-1] = B[i];
for (int d = 1; d <= N - L; ++d) {
for (int i = 1; i + d <= N; ++i) {
X[i] = X[i-1] + (A[i] != A[i + d]);
}
for (int i = 1; i + d + L - 1 <= N; ++i) {
int t = B[X[i + L - 1] - X[i - 1]];
if (t == -1) continue;
++ans[t][i];
++ans[t][i + d];
}
}
for (int i = 1; i < Q; ++i)
for (int j = 1; j <= N; ++j) ans[i][j] += ans[i-1][j];
for (int i = 0; i < Q; ++i) {
for (int j = 1; j <= N - L + 1; ++j) cout << ans[idx[i]][j] << ' ';
cout << '\n';
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
768 KB |
Output is correct |
2 |
Correct |
2 ms |
896 KB |
Output is correct |
3 |
Correct |
3 ms |
896 KB |
Output is correct |
4 |
Correct |
3 ms |
768 KB |
Output is correct |
5 |
Correct |
3 ms |
768 KB |
Output is correct |
6 |
Incorrect |
2 ms |
768 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
768 KB |
Output is correct |
2 |
Correct |
2 ms |
896 KB |
Output is correct |
3 |
Correct |
3 ms |
896 KB |
Output is correct |
4 |
Correct |
3 ms |
768 KB |
Output is correct |
5 |
Correct |
3 ms |
768 KB |
Output is correct |
6 |
Incorrect |
2 ms |
768 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
252 ms |
916 KB |
Output is correct |
2 |
Correct |
177 ms |
896 KB |
Output is correct |
3 |
Correct |
190 ms |
896 KB |
Output is correct |
4 |
Correct |
179 ms |
984 KB |
Output is correct |
5 |
Correct |
128 ms |
1016 KB |
Output is correct |
6 |
Correct |
165 ms |
1024 KB |
Output is correct |
7 |
Correct |
125 ms |
976 KB |
Output is correct |
8 |
Correct |
176 ms |
1024 KB |
Output is correct |
9 |
Correct |
175 ms |
1020 KB |
Output is correct |
10 |
Correct |
177 ms |
1024 KB |
Output is correct |
11 |
Correct |
19 ms |
860 KB |
Output is correct |
12 |
Correct |
122 ms |
1032 KB |
Output is correct |
13 |
Correct |
133 ms |
896 KB |
Output is correct |
14 |
Correct |
122 ms |
896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
252 ms |
916 KB |
Output is correct |
2 |
Correct |
177 ms |
896 KB |
Output is correct |
3 |
Correct |
190 ms |
896 KB |
Output is correct |
4 |
Correct |
179 ms |
984 KB |
Output is correct |
5 |
Correct |
128 ms |
1016 KB |
Output is correct |
6 |
Correct |
165 ms |
1024 KB |
Output is correct |
7 |
Correct |
125 ms |
976 KB |
Output is correct |
8 |
Correct |
176 ms |
1024 KB |
Output is correct |
9 |
Correct |
175 ms |
1020 KB |
Output is correct |
10 |
Correct |
177 ms |
1024 KB |
Output is correct |
11 |
Correct |
19 ms |
860 KB |
Output is correct |
12 |
Correct |
122 ms |
1032 KB |
Output is correct |
13 |
Correct |
133 ms |
896 KB |
Output is correct |
14 |
Correct |
122 ms |
896 KB |
Output is correct |
15 |
Correct |
224 ms |
956 KB |
Output is correct |
16 |
Correct |
163 ms |
1020 KB |
Output is correct |
17 |
Correct |
185 ms |
1024 KB |
Output is correct |
18 |
Correct |
182 ms |
1036 KB |
Output is correct |
19 |
Correct |
175 ms |
1040 KB |
Output is correct |
20 |
Correct |
181 ms |
1144 KB |
Output is correct |
21 |
Correct |
187 ms |
1024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
768 KB |
Output is correct |
2 |
Correct |
2 ms |
896 KB |
Output is correct |
3 |
Correct |
3 ms |
896 KB |
Output is correct |
4 |
Correct |
3 ms |
768 KB |
Output is correct |
5 |
Correct |
3 ms |
768 KB |
Output is correct |
6 |
Incorrect |
2 ms |
768 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |