Submission #309091

#	Time	Username	Problem	Language	Result	Execution time	Memory
309091		shivensinha4	Lottery (CEOI18_lot)	C++17	45 / 100	3043 ms	1144 KiB

lot

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#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 = 10000, MXQ = 100;
int ans[MXQ+1][MXN+1], nums[MXN+1], match[MXN+1], freq[MXN+3], qr[MXQ+1];
vi pos[MXN+1];

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;
	vector<ii> val(n);
	for_(i, 0, n) {
		cin >> nums[i];
		val[i] = {nums[i], i};
	}
	
	sort(val.begin(), val.end());
	int pt = -1;
	for_(i, 0, n) {
		if (i > 0 and val[i].first == val[i-1].first) nums[val[i].second] = pt;
		else nums[val[i].second] = ++pt;
	}
	
	for_(i, 0, n) pos[nums[i]].push_back(i);
	
	int q; cin >> q;
	for_(i, 0, q) cin >> qr[i];
	
	for_(i, 0, n-l+1) {
		memset(match, 0, sizeof(match)); memset(freq, 0, sizeof(freq));
		for_(j, 0, l) for (auto p: pos[nums[i+j]]) if (p >= j and p != i+j) match[p-j] += 1;
		int mx = 0;
		for_(j, 0, n-l+1) if (i != j) {
			freq[match[j]] += 1;
			mx = max(mx, match[j]);
		}
		for (int j = mx-1; j >= 0; j--) freq[j] += freq[j+1];
		for_(j, 0, q) ans[j][i] = freq[l-qr[j]];
	}
	
	for_(i, 0, q) {
		for_(j, 0, n-l+1) cout << ans[i][j] << " ";
		cout << endl;
	}
	
	cout << endl;

	return 0;
}

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