Submission #971625

#	Time	Username	Problem	Language	Result	Execution time	Memory
971625		Baytoro	Lottery (CEOI18_lot)	C++17	100 / 100	571 ms	8276 KiB

lot

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
const int N=1e4+6;
int a[N],ans[N][101];
void solve(){
	int n,l;
	cin>>n>>l;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int q;cin>>q;
	vector<pair<int,int> > v(q);
	vector<int> sv(q);
	for(int i=0;i<q;i++){
		cin>>v[i].fr;
		sv[i]=v[i].fr;
		v[i].sc=i;
	}
	sort(v.begin(),v.end());
	int last=0;
	vector<int> id(l+1);
	for(int i=0;i<=l;i++){
		while(last<q && v[last].fr<i){
			last++;
		}
		id[i]=last;
	}
	for(int i=1;i<=n-l;i++){
		int diff=0;
		for(int j=1;j<=l;j++){
			if(a[j]!=a[i+j]) diff++;
		}
		if(diff<=v.back().fr){
			ans[i+1][id[diff]]++;
			ans[1][id[diff]]++;
		}
		for(int j=2;j+i<=n-l+1;j++){
			if(a[j-1]!=a[j+i-1]) diff--;
			if(a[j+l-1]!=a[j+i+l-1]) diff++;
			if(diff<=v.back().fr){
				ans[j][id[diff]]++;
				ans[i+j][id[diff]]++;
			}
		}
		
	}
	for(int i=1;i<=n-l+1;i++) 
		for(int j=1;j<q;j++) 
			ans[i][j]+=ans[i][j-1];
	for(int i=0;i<q;i++){
		for(int j=1;j<=n-l+1;j++) cout<<ans[j][id[sv[i]]]<<' ';
		cout<<endl;
	}
}
signed main(){
	int t=1;//cin>>t;
	while(t--) solve();
}

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20