이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx,avx2")
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int N = 1e4 + 1;
int ans[102][N];
int low_bound[N];
int pref[N];
void solve(){
int n, len;
cin >> n >> len;
int m = n - len + 1;
vector<int> a(n);
for (int i = 0; i < n; i++){
cin >> a[i];
}
int q;
cin >> q;
vector<pair<int, int>> ks(q);
for (int i = 0; i < q; i++){
cin >> ks[i].first;
ks[i].second = i;
}
sort(ks.rbegin(), ks.rend());
for (int d = 0; d <= n; d++){
int i = 0;
while (i < q && ks[i].first >= d) i++;
low_bound[d] = i - 1;
}
for (int diff = -n; diff <= n; diff++){
if (diff == 0) continue;
int i = 0, j = diff;
int add = -1 * min(i, j);
if (add > 0) i += add, j += add;
for (; i < n && j < n; i++, j++){
if (a[i] == a[j]){
int lf = max(0, i - len + 1);
pref[lf]++;
if (i + 1 < m) pref[i + 1]--;
}
}
for (i = 0; i < m; i++){
if (i){
pref[i] += pref[i - 1];
pref[i - 1] = 0;
}
j = i + diff;
int d = len - pref[i];
if (j >= 0 && j < m){
int r = low_bound[d];
ans[0][i]++;
ans[r + 1][i]--;
}
}
pref[m - 1] = 0;
}
for (int j = 1; j < q; j++){
for (int i = 0; i < m; i++){
ans[j][i] += ans[j - 1][i];
}
}
for (int it = 0; it < q; it++){
int j = 0;
while (j < q && ks[j].second != it) j++;
for (int i = 0; i < m; i++){
cout << ans[j][i] << ' ';
}
cout << endl;
}
}
int main(){
ios_base::sync_with_stdio(false);
int t = 1;
//cin >> t;
while (t--){
solve();
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |