# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
541584 | UncoolAnon | Lottery (CEOI18_lot) | C++14 | 3 ms | 596 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;
void print(vector<int> a){
for(int x:a) cout << x << " ";
cout<<endl ;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
int n,l,q;
cin>>n>>l;
vector<int> a(n);
for(int&x:a) cin>>x;
cin>>q;
vector<vector<int>> answer(q,vector<int>(n-l+1));
vector<int> m(q);
for(int&x:m) cin>>x;
vector<int> dif(n-l+1);
for(int i=0;i+l-1<n;i++){
if(i==0){
for(int j=0;j+l-1<n;j++){
int d=0;
for(int k=j;k<j+l;k++) d+=(a[k]!=a[i+k-j]);
dif[j]=d;
}
}
else{
for(int j=n-1;j>0;j--){
if(j+l-1<n){
dif[j]=dif[j-1]-(a[j-1]!=a[i-1]);
dif[j]+=(a[j+l-1]!=a[i+l-1]);
}
}
dif[0]=0;
for(int j=0;j<l;j++)
dif[0]+=(a[i+j]!=a[j]);
}
//cout << i << " :" ; print(dif);
vector<int> prefix(n+1);
for(int&x:dif) prefix[x]++;
for(int i=1;i<=n;i++) prefix[i]+=prefix[i-1];
for(int query=0;query<q;query++)
answer[query][i]=prefix[m[query]]-1;
}
for(auto x:answer){
for(int y:x) cout<<y<<" ";
cout<<'\n';
}
return 0;
}
Compilation message (stderr)
# | 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... |