#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
struct state {
deque<int> vec, freq;
state (int n, int sz) : vec(n), freq(sz + 1) { freq[0] = n; }
void change (int pos, int val) {
if (0 <= pos && pos < vec.size())
freq[vec[pos]]--, vec[pos] += val, freq[vec[pos]]++;
}
void shift (int val) {
vec.push_front(val);
freq[val]++, freq[vec.back()]--;
vec.pop_back();
}
};
const int mn = 1e4 + 4;
vector<int> pos[mn];
int a[mn], ans[100][mn];
int calc (int u, int v, int k) {
int ans = 0;
for (int i = u, j = v, cnt = 0; cnt < k; i++, j++, cnt++)
if (a[i] == a[j]) ans++;
return ans;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, k; cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> a[i];
pos[a[i]].push_back(i);
}
int q; cin >> q;
vector<pii> qry(q);
for (int i = 0; i < q; i++) {
int dl; cin >> dl;
qry[i] = {dl, i};
}
sort(all(qry));
state helper(n - k + 1, k);
for (int i = 0; i < k; i++)
for (int p : pos[a[i]]) helper.change(p - i, 1);
for (int i = 0; i + k - 1 < n; i++) {
int iter = k + 1, cur = 0;
for (pii it : qry) {
int dl, id; tie(dl, id) = it;
int minSame = k - dl;
while (iter > minSame)
cur += helper.freq[--iter];
ans[id][i] = cur;
}
for (int p : pos[a[i]]) helper.change(p, -1);
if (i + k < n) {
for (int p : pos[a[i + k]]) helper.change(p - k, 1);
helper.shift(calc(0, i + 1, k));
}
}
for (int i = 0; i < q; i++) {
for (int j = 0; j + k - 1 < n; j++) cout << ans[i][j] - 1 << " ";
cout << "\n";
}
return 0;
}
Compilation message
lot.cpp: In member function 'void state::change(int, int)':
lot.cpp:18:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | if (0 <= pos && pos < vec.size())
| ~~~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
604 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Correct |
1 ms |
2652 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Runtime error |
1 ms |
860 KB |
Execution killed with signal 11 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
604 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Correct |
1 ms |
2652 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Runtime error |
1 ms |
860 KB |
Execution killed with signal 11 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
532 ms |
856 KB |
Output is correct |
2 |
Correct |
504 ms |
1112 KB |
Output is correct |
3 |
Correct |
128 ms |
860 KB |
Output is correct |
4 |
Runtime error |
1 ms |
1116 KB |
Execution killed with signal 11 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
532 ms |
856 KB |
Output is correct |
2 |
Correct |
504 ms |
1112 KB |
Output is correct |
3 |
Correct |
128 ms |
860 KB |
Output is correct |
4 |
Runtime error |
1 ms |
1116 KB |
Execution killed with signal 11 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
604 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Correct |
1 ms |
2652 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Runtime error |
1 ms |
860 KB |
Execution killed with signal 11 |
6 |
Halted |
0 ms |
0 KB |
- |