Submission #311770

#	Time	Username	Problem	Language	Result	Execution time	Memory
311770		shivensinha4	Lottery (CEOI18_lot)	C++17	100 / 100	1517 ms	8440 KiB

lot

#include <bits/stdc++.h> 
using namespace std; 
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'

const int MXN = 1e4, MXQ = 100;
int freq[MXQ+1][MXN+2];

int main() {
	#ifdef shiven
	freopen("test.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, l; cin >> n >> l;
	vi nums(n);
	for_(i, 0, n) cin >> nums[i];
	int q; cin >> q;
	vector<ii> qrs(q);
	for_(i, 0, q) {
		cin >> qrs[i].first;
		qrs[i].second = i;
	}
	
	sort(qrs.begin(), qrs.end());
	
	for_(d, 1, n+1) {
		vi temp(n);
		for_(j, d, n) if (nums[j] != nums[j-d]) temp[j] += 1;
		for_(i, d, n) temp[i] += temp[i-1];
		for_(j, d, n-l+1) {
			int dist = temp[j+l-1] - (j > 0 ? temp[j-1] : 0);
			int idx = lower_bound(qrs.begin(), qrs.end(), (ii) {dist, -1}) - qrs.begin();
			if (idx < q) {
				freq[qrs[idx].second][j] += 1; freq[qrs[idx].second][j-d] += 1;
			}
		}
	}
	
	for_(i, 0, q) for_(j, 0, n-l+1) if (i > 0) freq[qrs[i].second][j] += freq[qrs[i-1].second][j];
	
	for_(i, 0, q) {
		for_(j, 0, n-l+1) cout << freq[i][j] << " ";
		cout << endl;
	}

	return 0;
}

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