Submission #918557

#	Time	Username	Problem	Language	Result	Execution time	Memory
918557		PM1	Lottery (CEOI18_lot)	C++17	100 / 100	531 ms	8336 KiB

lot

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
const int mxn=1e4+4,mxq=102;
int n,q,ans[mxq][mxn],l;
pair<int,int>b[mxq];
int a[mxn],loc[mxn];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>l;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	cin>>q;
	for(int i=1;i<=q;i++){
		cin>>b[i].fr;
		b[i].sc=i;
	}
	sort(b+1,b+q+1);
	int p=1;
	for(int i=0;i<=l;i++){
		while(p<=q && b[p].fr<i)p++;
		loc[i]=p;
	}
	for(int k=1;k<=n-l;k++){
		int cnt=0;
		for(int i=0;i<l;i++)
			if(a[1+i]==a[1+k+i])cnt++;
		ans[b[loc[l-cnt]].sc][1]++;
		ans[b[loc[l-cnt]].sc][k+1]++;
		//cout<<l-cnt<<" ";
		for(int i=2;i+k<=n-l+1;i++){
			if(a[i+l-1]==a[i+k+l-1])cnt++;
			if(a[i-1]==a[i+k-1])cnt--;
			ans[b[loc[l-cnt]].sc][i]++;
			ans[b[loc[l-cnt]].sc][i+k]++;
			//cout<<l-cnt<<" ";
		}
		//cout<<endl;
	}
	for(int i=2;i<=q;i++)
		for(int j=1;j<=n-l+1;j++)
			ans[b[i].sc][j]+=ans[b[i-1].sc][j];

	for(int i=1;i<=q;i++){
		for(int j=1;j<=n-l+1;j++)
			cout<<ans[i][j]<<" ";
		cout<<'\n';
	}
}

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