This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
signed main() {
cin.tie(0)->sync_with_stdio(0);
int n, m;
cin >> n >> m;
vector<int> arr(n);
for (int& i : arr) cin >> i;
int q;
cin >> q;
vector<int> ask(q), asks;
for (int& i : ask) cin >> i;
asks = ask;
sort(asks.begin(), asks.end());
vector<int> rev(n+1, -1);
{
int k = 0;
for (int i : asks) {
rev[i] = k;
k++;
}
}
for (int i = n-1; i >= 0; i--) {
if (rev[i] == -1)
rev[i] = rev[i+1];
if (rev[i] == -1) rev[i] = 100;
}
vector<array<int, 101>> cnt(n, {{}});
for (int b = 1; b + m <= n; b++) {
int al = 0, ar = m-1;
int diff = 0;
int bl = b, br = b + m-1;
for (int i = 0; i < m; i++)
diff += arr[al+i] != arr[bl+i];
// cout << "[" << al << ".." << ar << "] and [" << bl << ".." << br << "] with " << diff << "\n";
cnt[al][rev[diff]]++;
cnt[bl][rev[diff]]++;
while (br < n-1) {
diff -= arr[al++] != arr[bl++];
diff += arr[++ar] != arr[++br];
// cout << "[" << al << ".." << ar << "] and [" << bl << ".." << br << "] with " << diff << "\n";
cnt[al][rev[diff]]++;
cnt[bl][rev[diff]]++;
}
}
for (int i = 0; i < n; i++) {
for (int j = 1; j <= 100; j++)
cnt[i][j] += cnt[i][j-1];
}
for (int k : ask) {
for (int i = 0; i + m <= n; i++) {
cout << cnt[i][rev[k]] << ' ';
}
cout << '\n';
}
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... |