Submission #1214458

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214458		goduadzesaba	Lottery (CEOI18_lot)	C++20	100 / 100	345 ms	20368 KiB

lot

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e4+5,M=1e2+5,mod=1e9+7,inf=2e18;
int n,l,qq,a[N],q[N][M],dp[N],nx[N],ans[M][N]; pair<int,int> p[N];
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n>>l;
	for (int i=1; i<=n; i++) cin>>a[i];
	cin>>qq;
	for (int i=1; i<=qq; i++){
		cin>>p[i].first; p[i].second=i;
	}
	sort(p+1,p+qq+1); int x=qq; p[qq+1]={inf,inf};
	for (int i=N; i>0; i--){
		while (p[x].first>=i) x--; x++;
		nx[i]=x;
		//cout<<i<<" "<<nx[i]<<"\n";
	}
	for (int k=1; k<=n-l; k++){
		for (int i=1; i<=n; i++) dp[i]=0;
		for (int i=1; i<=l; i++) dp[1]+=(a[i]!=a[i+k]);
		q[1][nx[dp[1]]]++; q[k+1][nx[dp[1]]]++;
		//cout<<"1 "<<dp[1]<<"\n";
		for (int i=2; i+k<=n-l+1; i++){
			dp[i]=dp[i-1]; dp[i]-=(a[i-1]!=a[i+k-1]);
			dp[i]+=(a[i+l-1]!=a[i+l-1+k]);
			
			q[i][nx[dp[i]]]++; q[i+k][nx[dp[i]]]++;
			//cout<<i<<" "<<dp[i]<<"\n";
		}
	}
	for (int j=1; j<=qq; j++){
		for (int i=1; i<=n-l+1; i++){
			q[i][j]+=q[i][j-1];
			//cout<<i<<" "<<j<<" "<<q[i][j]<<" "<<p[j].second<<"\n";
			ans[p[j].second][i]=q[i][j];
		}
	}
	for (int i=1; i<=qq; 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