#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e4 + 5;
int N, L, a[maxN], k[maxN], Q, M;
namespace subtask1{
bool check(){
return N <= 300;
}
int res[303][303];
void solve(){
for(int i = 1; i <= M; ++i){
for(int j = i + 1; j <= M; ++j){
int cnt = 0;
for(int x = 0; x < L; ++x){
if(a[i + x] != a[j + x])++cnt;
}
res[i][cnt]++;
res[j][cnt]++;
}
}
for(int i = 1; i <= M; ++i)for(int j = 1; j <= L; ++j)res[i][j] += res[i][j - 1];
for(int i = 1; i <= Q; ++i){
for(int j = 1; j <= M; ++j)cout << res[j][k[i]] << ' ';cout << "\n";
}
}
}
namespace subtask2{
bool check(){
return N <= 2000;
}
int diff[2001][2001];// doan [i va
int res[2001][2001];
void solve(){
for(int i = 1; i <= M; ++i){
for(int x = 1; x < L; ++x){
if(a[i] != a[i + x]){
diff[max(1, i + 1 - x)][x]++;
diff[i + 1][x]--;
}
}
}
}
}
namespace subtask3{
bool check(){
return Q == 1 && k[1] == 0;
}
int comp[maxN];
const int BASE = 10000;
const int mod = 1e9 + 9;
const long long MS = 1ll * mod * mod;
#define hash __hash
int hash[maxN], power[maxN];
int getHash(int i, int j){
return (hash[j] - 1ll * hash[i - 1] * power[j - i + 1] + MS) % mod;
}
pair<int, int> d[maxN];
int cnt[maxN], res[maxN];
void solve(){
for(int i = 1; i <= N; ++i)comp[i] = a[i];
sort(comp + 1, comp + 1 + N);
for(int i = 1; i <= N; ++i){
a[i] = lower_bound(comp + 1, comp + 1 + N, a[i]) - comp;
}
power[0] = 1;
for(int i = 1; i <= N; ++i){
power[i] = 1ll * power[i - 1] * BASE % mod;
hash[i] = (1ll * hash[i - 1] * BASE + a[i]) % mod;
}
for(int i = 1; i <= M; ++i){
d[i] = {getHash(i, i + L - 1), i};
comp[i] = d[i].first;
}
sort(d + 1, d + 1 + M);
sort(comp + 1, comp + 1 + M);
for(int i = 1; i <= M; ++i){
d[i].first = lower_bound(comp + 1, comp + 1 + M, d[i].first) - comp;
cnt[d[i].first]++;
}
for(int i = 1; i <= M; ++i)res[d[i].second] = cnt[d[i].first];
for(int i = 1; i <= M; ++i)cout << --res[i] << ' ';
}
}
int main(){
freopen("lot.inp", "r", stdin);
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> N >> L;
M = N - L + 1;
for(int i = 1; i <= N; ++i)cin >> a[i];
cin >> Q;
for(int i = 1; i <= Q; ++i){
cin >> k[i];
}
if(subtask1 :: check()) return subtask1 :: solve(), 0;
if(subtask3 :: check()) return subtask3 :: solve(), 0;
return 0;
}
Compilation message
lot.cpp: In function 'void subtask1::solve()':
lot.cpp:25:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
25 | for(int j = 1; j <= M; ++j)cout << res[j][k[i]] << ' ';cout << "\n";
| ^~~
lot.cpp:25:68: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
25 | for(int j = 1; j <= M; ++j)cout << res[j][k[i]] << ' ';cout << "\n";
| ^~~~
lot.cpp: In function 'int main()':
lot.cpp:87:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
87 | freopen("lot.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
