# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
311063 | tigicha | Lottery (CEOI18_lot) | C++14 | 0 ms | 0 KiB |
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;
int n, l, q, k, t, a[100005], b[100005], mas[100005], array[100005][105], ans[100005][105];
pair<int, int>ar[100005];
int main(){
cin>>n>>l;
for(int i=1; i<=n; i++)
cin>>a[i];
cin>>q;
for(int i=1; i<=q; i++){
cin>>ar[i].first;
ar[i].second=i;
}
sort(ar+1, ar+q+1);
k=1;
for(int i=0; i<=n; i++){
while(ar[k].first<i && k<=q)
k++;
mas[i]=k;
}
for(int i=1; i<=n; i++){
for(int j=1; j<=n-i; j++){
b[j]=0;
if(a[j]!=a[i+j])
b[j]=1;
}
for(int j=1; j<=n-i; j++){
b[j]+=b[j-1];
if(j>=l){
t=b[j]-b[j-l];
array[j-l+1][mas[t]]++;
array[j+i-l+1][mas[t]]++;
}
}
}
for(int i=1; i<=q; i++)
for(int j=1; j<=n-l+1; j++)
ans[j][ar[i].second]=array[j][i]+ans[j][ar[i-1].second];
for(int i=1; i<=q; i++){
for(int j=1; j<=n-l+1; j++)
cout<<ans[j][i]<<" ";
cout<<endl;
}
return 0;
}