Submission #810587

#	Time	Username	Problem	Language	Result	Execution time	Memory
810587		welleyth	Lottery (CEOI18_lot)	C++17	100 / 100	850 ms	8328 KiB

lot

#include <bits/stdc++.h>

using namespace std;

constexpr int N = (int)7e5;

void solve(){
	int n,l;
	cin >> n >> l;

	int a[n+1];
	for(int i = 1; i <= n; i++) cin >> a[i];

	vector<int> queries;
	vector<int> K;
	int q;
	cin >> q;
	for(int i = 0; i < q; i++){
		int k;
		cin >> k;
		queries.push_back(k);
		K.push_back(k);
	}

	sort(K.begin(),K.end());

	int pref[n+1];
	int cntDiff[n+1][q+1];
	memset(cntDiff,0,sizeof cntDiff);

	for(int d = 1; d < n; d++){
		memset(pref,0,sizeof pref);
		for(int i = 1; i + d <= n; i++){
			pref[i] = pref[i-1] + (a[i] != a[i+d]);
		}
		for(int i = 1; i + d <= n - l + 1; i++){
			int cnt = pref[i+l-1] - pref[i-1];
			int id = lower_bound(K.begin(),K.end(),cnt) - K.begin();
			cntDiff[i][id]++;
			cntDiff[i+d][id]++;
		}
	}

	int ans[q];

	for(int i = 1; i <= n; i++){
		for(int j = 1; j < q; j++){
			cntDiff[i][j] += cntDiff[i][j-1];
		}
	}

	for(auto& k : queries){
		int id = lower_bound(K.begin(),K.end(),k) - K.begin();
		for(int i = 1; i <= n-l+1; i++){
			cout << cntDiff[i][id] << " ";
		}
		cout << "\n";
	}

	return;
}

signed main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	int tests = 1;
	for(int test = 1; test <= tests; test++){
		solve();
	}

	return 0;
}
/**
 * dist(1,2) = (a[1] != a[2]) + (a[2] != a[3]) + (a[3] != a[4]) + ... + (a[l] != a[l+1])
 * dist(1,3) = (a[1] != a[3]) + (a[2] != a[4])
 * 
 * 
 * 

**/

Compilation message (stderr)

lot.cpp: In function 'void solve()':
lot.cpp:44:6: warning: unused variable 'ans' [-Wunused-variable]
   44 |  int ans[q];
      |      ^~~

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