Submission #455171

#	Time	Username	Problem	Language	Result	Execution time	Memory
455171		Nima_Naderi	Lottery (CEOI18_lot)	C++14	100 / 100	940 ms	12488 KiB

lot

//In the name of God
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MXN = 1e4 + 10;
const ll MXQ = 100 + 10;
ll n, k, q;
ll A[MXN], f[MXN], Q[MXN];
ll diff[MXN], cnt[MXN];
ll ANS[MXQ][MXN], ps[MXN];
void Save(ll p){
	ps[0] = cnt[0];
	for(int i = 1; i <= n; i ++) ps[i] = ps[i - 1] + cnt[i];
	for(int i = 1; i <= q; i ++) ANS[i][p] += ps[Q[i]];
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
	cin >> n >> k;
	for(int i = 1; i <= n; i ++) cin >> A[i];
	cin >> q;
	for(int i = 1; i <= q; i ++) cin >> Q[i];
	for(int j = 2; j + k - 1 <= n; j ++){
		for(int l = 0; l < k; l ++) diff[j - 1] += (A[1 + l] != A[j + l]);
		cnt[diff[j - 1]] ++;
	}
	Save(1);
	for(int i = 2; i <= n - k + 1; i ++){
		cnt[diff[n - k + 1 - i + 1]] --;
		for(int t = 1; i + t + k - 1 <= n; t ++){
			cnt[diff[t]] --;
			diff[t] -= (A[i - 1] != A[i + t - 1]);
			diff[t] += (A[i - 1 + k] != A[i + t - 1 + k]);
			cnt[diff[t]] ++;
		}
		Save(i);
	}
	memset(cnt, 0, sizeof cnt), memset(diff, 0, sizeof diff);
	for(int j = 1; j + k - 1 < n; j ++){
		for(int l = 0; l < k; l ++) diff[(n - k + 1) - j] += (A[(n - k + 1) + l] != A[j + l]);
		cnt[diff[(n - k + 1) - j]] ++;
	}
	Save(n - k + 1);
	for(int i = n - k; i >= 1; i --){
		cnt[diff[i]] --;
		for(int t = 1; t <= i - 1; t ++){
			cnt[diff[t]] --;
			diff[t] += (A[i] != A[i - t]);
			diff[t] -= (A[i + k] != A[i - t + k]);
			cnt[diff[t]] ++;
		}
		Save(i);
	}
	for(int i = 1; i <= q; i ++){
		for(int j = 1; j <= n - k + 1; j ++) cout << ANS[i][j] << " \n"[j == n - k + 1];
	}
	return 0;
}
// N.N wants gold medal !

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