#include <bits/stdc++.h>
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
//#define endl '\n'
const int MXN = 10000, MXQ = 100;
int ans[MXQ+1][MXN+1], nums[MXN+1], match[MXN+1];
ii qr[MXQ+1];
vi pos[MXN+1];
int main() {
#ifdef shiven
freopen("test.in", "r", stdin);
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, l; cin >> n >> l;
vector<ii> val(n);
for_(i, 0, n) {
cin >> nums[i];
val[i] = {nums[i], i};
}
sort(val.begin(), val.end());
int pt = -1;
for_(i, 0, n) {
if (i > 0 and val[i].first == val[i-1].first) nums[val[i].second] = pt;
else nums[val[i].second] = ++pt;
}
for_(i, 0, n) pos[nums[i]].push_back(i);
int q; cin >> q;
for_(i, 0, q) {
cin >> qr[i].first;
qr[i].second = i;
}
sort(qr, qr+q);
vi close(qr[q-1].first+1);
pt = q-1;
for (int i = close.size()-1; i >= 0; i--) {
if (pt >= 0 and i == qr[pt].first) close[i] = qr[pt--].second;
else close[i] = close[i+1];
}
//for (int i: close) cout << i << " " ;
//cout << endl;
for_(i, 0, n-l+1) {
memset(match, 0, sizeof(match));
for_(j, 0, l) for (auto p: pos[nums[i+j]]) {
if (p == i+j) break;
if (p >= j) match[p-j] += 1;
}
for_(j, 0, i) {
if (l-match[j] >= qr[q-1].first) continue;
//int pt = close[l-match[j]];
int pt2 = qr[lower_bound(qr, qr+q, (ii) {l-match[j], -1})-qr].second;
//cout << pt << " " << qr[pt2].second << endl;
//assert(qr[pt2].second == pt);
ans[pt2][i] += 1;
ans[pt2][j] += 1;
}
}
for_(qq, 1, q) for_(i, 0, n-l+1) ans[qr[qq].second][i] += ans[qr[qq-1].second][i];
for_(i, 0, q) {
for_(j, 0, n-l+1) cout << ans[i][j] << " ";
cout << endl;
}
cout << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
640 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
768 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
640 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
768 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
387 ms |
864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
387 ms |
864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
640 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
768 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
