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>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
signed main(){
ios_base::sync_with_stdio();
cin.tie(0);cout.tie(0);
int n,l,q;
cin>>n>>l;
vector <int> a(n+1);
for(int i=1;i<=n;i++)cin>>a[i];
cin>>q;
vector <int> k(q),v;
for(int i=0;i<q;i++){
cin>>k[i];
v.pb(k[i]);
}
sort(all(v));
vector <vector <int> > ans(n+1,vector <int> (q));
for(int i=1;i<=n;i++){
if(i+l-1<=n){
int res=0;
int ind=1;
for(int j=i;j<i+l;j++){
res+=(a[ind]!=a[j]);
ind++;
}
auto it=lower_bound(all(v),res);
if(it!=v.end())ans[1][it-v.begin()]++;
int x=2,y=i+1;
while(x<=n && y<=n && x+l-1<=n && y+l-1<=n){
int new_res=res-(a[x-1]!=a[y-1])+(a[x+l-1]!=a[y+l-1]);
res=new_res;
auto it=lower_bound(all(v),res);
if(it!=v.end())ans[x][it-v.begin()]++;
x++;
y++;
}
}
}
for(int i=2;i<=n;i++){
if(i+l-1<=n){
int res=0;
int ind=1;
for(int j=i;j<i+l;j++){
res+=(a[ind]!=a[j]);
ind++;
}
auto it=lower_bound(all(v),res);
if(it!=v.end())ans[i][it-v.begin()]++;
int x=i+1,y=2;
while(x<=n && y<=n && x+l-1<=n && y+l-1<=n){
int new_res=res-(a[x-1]!=a[y-1])+(a[x+l-1]!=a[y+l-1]);
res=new_res;
auto it=lower_bound(all(v),res);
if(it!=v.end())ans[x][it-v.begin()]++;
x++;
y++;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<q;j++)ans[i][j]+=ans[i][j-1];
}
for(int i=0;i<q;i++){
auto pos=lower_bound(all(v),k[i])-v.begin();
for(int j=1;j<=n-l+1;j++){
cout<<ans[j][pos]-1<<" ";
}
cout<<"\n";
}
}
/*
6 2
1 2 1 3 2 1
2
1
2
*/
# | 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... |