Submission #166300

#	Time	Username	Problem	Language	Result	Execution time	Memory
166300		Eae02	Lottery (CEOI18_lot)	C++14	100 / 100	2344 ms	13048 KiB

lot

#include <bits/stdc++.h>
#define all(x) begin(x),end(x)
using namespace std;

int main() {
	int n, l;
	cin >> n >> l;
	
	vector<int> a(n);
	for (int i = 0; i < n; i++)
		cin >> a[i];
	
	int q;
	cin >> q;
	vector<int> queriesK(q);
	for (int i = 0; i < q; i++) {
		cin >> queriesK[i];
	}
	
	vector<int> distinctK = queriesK;
	sort(all(distinctK));
	distinctK.erase(unique(all(distinctK)), distinctK.end());
	
	vector<vector<int>> sm;
	sm.reserve(n);
	for (int i = 0; i < n; i++)
		sm.emplace_back(distinctK.size() + 1);
	
	vector<int> diffCount(n - l + 1, 0);
	auto applyDiff = [&] (int i0) {
#ifdef LOCAL
		for (int i = i0 + 1; i + l <= n; i++) {
			int d = 0;
			for (int j = 0; j < l; j++) {
				if (a[i0 + j] != a[i + j])
					d++;
			}
			if (d != diffCount[i]) {
				cerr << "Error between " << i0 << " " << i << " got " << diffCount[i] << " exp " << d << "\n";
				abort();
			}
		}
#endif
		
		for (int i = i0 + 1; i + l <= n; i++) {
			int kIdx = lower_bound(all(distinctK), diffCount[i]) - distinctK.begin();
			sm[i0][kIdx]++;
			sm[i][kIdx]++;
		}
	};
	
	for (int ist = 1; ist + l <= n; ist++) {
		for (int j = 0; j < l; j++) {
			if (a[j] != a[ist + j])
				diffCount[ist]++;
		}
	}
	applyDiff(0);
	
	for (int i0 = 1; i0 + l <= n; i0++) {
		for (int i1 = n - l; i1 > i0; i1--) {
			diffCount[i1] = diffCount[i1 - 1];
			if (a[i0 - 1] != a[i1 - 1])
				diffCount[i1]--;
			if (a[i0 + l - 1] != a[i1 + l - 1])
				diffCount[i1]++;
		}
		applyDiff(i0);
	}
	
	vector<vector<int>> prefixSum(n);
	for (int i = 0; i < n; i++) {
		prefixSum[i].resize(sm[i].size() + 1, 0);
		for (int j = 0; j < sm[i].size(); j++) {
			prefixSum[i][j + 1] = prefixSum[i][j] + sm[i][j];
		}
	}
	
	for (int k : queriesK) {
		int kIdx = (lower_bound(all(distinctK), k) - distinctK.begin()) + 1;
		for (int i = 0; i < n - l + 1; i++) {
			cout << prefixSum[i][kIdx] << " ";
		}
		cout << "\n";
	}
}

Compilation message (stderr)

lot.cpp: In function 'int main()':
lot.cpp:74:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < sm[i].size(); j++) {
                   ~~^~~~~~~~~~~~~~

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