oj.uz

Submission #309271

# Submission time Handle Problem Language Result Execution time Memory
309271 2020-10-03T05:00:14 Z shivensinha4 Lottery (CEOI18_lot) C++17
0 / 100
 3000 ms 1012 KB 
#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];
ii 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].first;
		qr[i].second = i;
	}
	
	sort(qr, qr+q);
	vi close(qr[q-1].first+1);
	pt = q-1;
	for (int i = close.size()-1; i >= 0; i--) {
		if (pt >= 0 and i == qr[pt].first) close[i] = qr[pt--].second;
		else close[i] = close[i+1];
	}
	//for (int i: close) cout << i << " " ;
	//cout << endl;
	
	for_(i, 0, n-l+1) {
		memset(match, 0, sizeof(match));
		for_(j, 0, l) for (auto p: pos[nums[i+j]]) {
			if (p == i+j) break;
			if (p >= j) match[p-j] += 1;
		}
		for_(j, 0, i) {
			if (l-match[j] > qr[q-1].first) continue;
			int pt = close[l-match[j]];
			//int pt2 = qr[lower_bound(qr, qr+q, (ii) {l-match[j], -1})-qr].second;
			//cout << pt << " " << qr[pt2].second << endl;
			//assert(qr[pt2].second == pt);
			ans[pt][i] += 1;
			ans[pt][j] += 1;
		}
	}
	
	for_(qq, 1, q) for_(i, 0, n-l+1) ans[qr[qq].second][i] += ans[qr[qq-1].second][i];
	
	for_(i, 0, q) {
		for_(j, 0, n-l+1) cout << ans[i][j] << " ";
		cout << endl;
	}
	
	cout << endl;
 
	return 0;
}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 768 KB Output is correct
4 Correct 1 ms 640 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Incorrect 1 ms 640 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 768 KB Output is correct
4 Correct 1 ms 640 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Incorrect 1 ms 640 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 888 KB Output is correct
2 Correct 596 ms 1012 KB Output is correct
3 Correct 123 ms 888 KB Output is correct
4 Correct 248 ms 888 KB Output is correct
5 Execution timed out 3066 ms 768 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 888 KB Output is correct
2 Correct 596 ms 1012 KB Output is correct
3 Correct 123 ms 888 KB Output is correct
4 Correct 248 ms 888 KB Output is correct
5 Execution timed out 3066 ms 768 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 768 KB Output is correct
4 Correct 1 ms 640 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Incorrect 1 ms 640 KB Output isn't correct
7 Halted 0 ms 0 KB -