Submission #824812

#	Time	Username	Problem	Language	Result	Execution time	Memory
824812		dxz05	Lottery (CEOI18_lot)	C++17	100 / 100	1221 ms	8316 KiB

lot

#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx,avx2")
 
#include <bits/stdc++.h>
 
using namespace std;
 
const int MOD = 1e9 + 7;
 
const int N = 1e4 + 1;
int ans[102][N];

int low_bound[N];
int pref[N];

void solve(){
	int n, len;
	cin >> n >> len;
	
	int m = n - len + 1;
	
	vector<int> a(n);
	for (int i = 0; i < n; i++){
		cin >> a[i];
	}
	
	int q;
	cin >> q;
	
	vector<pair<int, int>> ks(q);
	for (int i = 0; i < q; i++){
		cin >> ks[i].first;
		ks[i].second = i;
	}
	
	sort(ks.rbegin(), ks.rend());
	
	for (int d = 0; d <= n; d++){
		int i = 0;
		while (i < q && ks[i].first >= d) i++;
		low_bound[d] = i - 1;
	}
	
	for (int diff = -n; diff <= n; diff++){
		if (diff == 0) continue;
		
		int i = 0, j = diff;
		int add = -1 * min(i, j);
		if (add	> 0) i += add, j += add;
		
		for (; i < n && j < n; i++, j++){
			if (a[i] == a[j]){
				int lf = max(0, i - len + 1);
				pref[lf]++;
				if (i + 1 < m) pref[i + 1]--;
			}
		}
		
		for (i = 0; i < m; i++){
			if (i){
				pref[i] += pref[i - 1];
				pref[i - 1] = 0;
			}
			
			j = i + diff;
			
			int d = len - pref[i];
			if (j >= 0 && j < m){
				int r = low_bound[d];
				ans[0][i]++;
				ans[r + 1][i]--;
			}
		}
		
		pref[m - 1] = 0;
	}
	
	for (int j = 1; j < q; j++){
		for (int i = 0; i < m; i++){
			ans[j][i] += ans[j - 1][i];
		}
	}
	
	for (int it = 0; it < q; it++){
		int j = 0;
		while (j < q && ks[j].second != it) j++;
		
		for (int i = 0; i < m; i++){
			cout << ans[j][i] << ' ';
		}
		cout << endl;
	}
}
 
int main(){
	ios_base::sync_with_stdio(false);
	
	int t = 1;
	//cin >> t;
	
	while (t--){
		solve();
	}
	
    return 0;
}

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