Submission #1180209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180209		PieArmy	Lottery (CEOI18_lot)	C++20	100 / 100	345 ms	9172 KiB

lot

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
using namespace std;

int n,l,q;
int arr[10023];
int Q[123],per[123];
int ans[10023][123];
int go[10023];
int dif[10023];

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	cin>>n>>l;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
	}
	cin>>q;
	for(int i=1;i<=q;i++){
		cin>>Q[i];
	}
	Q[q+1]=l+1;
	iota(per,per+q+1,1);
	sort(per,per+q+1,[&](const int &x,const int &y){
		return Q[x]<Q[y];
	});
	int loc=0;
	for(int i=0;i<=q;i++){
		while(loc<=Q[per[i]]){
			go[loc]=i;
			loc++;
		}
	}
	for(int i=1;i<=n-l;i++){
		for(int j=1;j+i<=n;j++){
			dif[j]=dif[j-1]+(arr[j]!=arr[j+i]);
		}
		for(int j=l;j<=n;j++){
			if(j+i<=n)ans[j][go[dif[j]-dif[j-l]]]++;
			if(j-l-i>=0)ans[j][go[dif[j-i]-dif[j-i-l]]]++;
		}
	}
	for(int i=1;i<q;i++){
		for(int j=l;j<=n;j++){
			ans[j][i]+=ans[j][i-1];
		}
	}
	for(int i=1;i<=q;i++){
		int pos=0;
		while(per[pos]!=i)pos++;
		for(int j=l;j<=n;j++)
			cout<<ans[j][pos]<<" ";
		cout<<endl;
	}
}

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