Submission #1214289

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214289		vako_p	Lottery (CEOI18_lot)	C++20	100 / 100	275 ms	20224 KiB

lot

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define sd second
#define debug(x) cerr << #x << "----> " << x << endl;
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("O3")

const int mxN = 10005;
ll n,l,q,idx[mxN],idx1[mxN],ans[105][mxN],p[mxN][105],a[mxN];
pair<ll,ll> qq[105];
 
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 >> qq[i].ff;
		qq[i].ff = l - qq[i].ff;
		qq[i].sd = i;
	}
	sort(qq + 1, qq + q + 1);
	for(int i = 1; i <= q; i++) idx1[i] = qq[i].sd;
	for(int i = 0; i <= l; i++){
		for(int j = q; j >= 1; j--){
			if(qq[j].ff <= i){
				idx[i] = j;
				break;
			}
		} 
	}
	for(int i = 2; i <= n - l + 1; i++){
		ll last = 0;
		for(int j = 0; j < l; j++) last += (a[1 + j] == a[i + j]);
		p[1][idx[last]]++;
		p[i][idx[last]]++;
//		cout << 1 << ' ' << i << "----> " << last << '\n';
		for(int j = 1; i + j <= n - l + 1; j++){
			last += (a[i + j + l - 1] == a[j + l]) - (a[j] == a[i + j - 1]);
//			cout << j + 1 << ' ' << i + j << "---> " << last << ' ' << idx[last] << '\n';
			p[j + 1][idx[last]]++;
			p[i + j][idx[last]]++;
		}
	}
	for(int i = 1; i <= n - l + 1; i++){
		for(int j = q; j >= 1; j--){
			p[i][j] += p[i][j + 1];
			ans[idx1[j]][i] = p[i][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