#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[i] = qry[i].second;
}
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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
768 KB |
Output is correct |
2 |
Incorrect |
2 ms |
896 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
768 KB |
Output is correct |
2 |
Incorrect |
2 ms |
896 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
249 ms |
896 KB |
Output is correct |
2 |
Correct |
180 ms |
896 KB |
Output is correct |
3 |
Correct |
172 ms |
896 KB |
Output is correct |
4 |
Correct |
169 ms |
904 KB |
Output is correct |
5 |
Correct |
105 ms |
896 KB |
Output is correct |
6 |
Correct |
168 ms |
1016 KB |
Output is correct |
7 |
Correct |
124 ms |
892 KB |
Output is correct |
8 |
Correct |
173 ms |
896 KB |
Output is correct |
9 |
Correct |
172 ms |
908 KB |
Output is correct |
10 |
Correct |
171 ms |
940 KB |
Output is correct |
11 |
Correct |
14 ms |
896 KB |
Output is correct |
12 |
Correct |
118 ms |
888 KB |
Output is correct |
13 |
Correct |
121 ms |
896 KB |
Output is correct |
14 |
Correct |
120 ms |
896 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
249 ms |
896 KB |
Output is correct |
2 |
Correct |
180 ms |
896 KB |
Output is correct |
3 |
Correct |
172 ms |
896 KB |
Output is correct |
4 |
Correct |
169 ms |
904 KB |
Output is correct |
5 |
Correct |
105 ms |
896 KB |
Output is correct |
6 |
Correct |
168 ms |
1016 KB |
Output is correct |
7 |
Correct |
124 ms |
892 KB |
Output is correct |
8 |
Correct |
173 ms |
896 KB |
Output is correct |
9 |
Correct |
172 ms |
908 KB |
Output is correct |
10 |
Correct |
171 ms |
940 KB |
Output is correct |
11 |
Correct |
14 ms |
896 KB |
Output is correct |
12 |
Correct |
118 ms |
888 KB |
Output is correct |
13 |
Correct |
121 ms |
896 KB |
Output is correct |
14 |
Correct |
120 ms |
896 KB |
Output is correct |
15 |
Correct |
216 ms |
908 KB |
Output is correct |
16 |
Correct |
161 ms |
896 KB |
Output is correct |
17 |
Correct |
182 ms |
1016 KB |
Output is correct |
18 |
Correct |
170 ms |
944 KB |
Output is correct |
19 |
Correct |
170 ms |
1016 KB |
Output is correct |
20 |
Correct |
171 ms |
896 KB |
Output is correct |
21 |
Correct |
169 ms |
900 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
768 KB |
Output is correct |
2 |
Incorrect |
2 ms |
896 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |