oj.uz

Submission #77977

# Submission time Handle Problem Language Result Execution time Memory
77977 2018-10-01T14:44:58 Z aminra Lottery (CEOI18_lot) C++14
35 / 100
 908 ms 2520 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MOD = (int)1e9 + 7;
const int MAXN = (int)1e4 + 3;
const int MAXS = (int)107;
const int infint = (int)1e9;
const ll inf = (ll)1e18;
int a[MAXN], n, cur[MAXN], q, ans[MAXS][MAXN], perm[MAXN], l;
struct query{
	int val, idx;
} Q[MAXS];
bool cmp(query a, query b)
{
	return a.val < a.idx;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> l;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	cin >> q;
	for (int i = 0; i < q; i++)
	{
		cin >> Q[i].val;
		Q[i].idx = i;
	}
	sort(Q, Q + q, cmp);
	vector<int> v;
	for (int i = 0; i < q; i++)
		v.push_back(Q[i].val);
	
	for (int i = 0; i < q; i++)
		for (int j = 0; j < n; j++)
			ans[i][j] = 0;
	
	for (int i = 1; i < n; i++)
	{
		memset(cur, 0, sizeof cur);
		for (int j = 0; j + i < n; j++)
			if(a[i + j] != a[j])
			{
				cur[j]++;
				if(j >= l)
					cur[j - l]--;
			}
		for (int j = n - i - 1; j >= 0; j--)
			cur[j] += cur[j + 1];
		for (int j = 0; j + i <= n - l; j++)
		{
			//dist[j][i + j] = cur[j]
			int idx = lower_bound(v.begin(), v.end(), cur[j]) - v.begin() - 1;
			if(idx == -1)
				continue;
			ans[idx][j]++, ans[idx][i + j]++;
		}
	}
	for (int i = q - 1; i >= 0; i--)
		for (int j = 0; j < n; j++)
			ans[i][j] += ans[i + 1][j];
	for (int i = 0; i < q; i++)
		perm[Q[i].idx] = i;
	for (int i = 0; i < q; i++)
	{
		for (int j = 0; j < n - l + 1; j++)
			cout << n - l - ans[perm[i]][j] << " ";
		cout << "\n";
	}
}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 508 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 508 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 908 ms 644 KB Output is correct
2 Correct 785 ms 760 KB Output is correct
3 Correct 550 ms 760 KB Output is correct
4 Correct 497 ms 912 KB Output is correct
5 Correct 279 ms 1008 KB Output is correct
6 Correct 451 ms 1128 KB Output is correct
7 Correct 227 ms 1244 KB Output is correct
8 Correct 250 ms 1388 KB Output is correct
9 Correct 452 ms 1488 KB Output is correct
10 Correct 468 ms 1600 KB Output is correct
11 Correct 46 ms 1600 KB Output is correct
12 Correct 312 ms 1712 KB Output is correct
13 Correct 320 ms 1712 KB Output is correct
14 Correct 343 ms 1876 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 908 ms 644 KB Output is correct
2 Correct 785 ms 760 KB Output is correct
3 Correct 550 ms 760 KB Output is correct
4 Correct 497 ms 912 KB Output is correct
5 Correct 279 ms 1008 KB Output is correct
6 Correct 451 ms 1128 KB Output is correct
7 Correct 227 ms 1244 KB Output is correct
8 Correct 250 ms 1388 KB Output is correct
9 Correct 452 ms 1488 KB Output is correct
10 Correct 468 ms 1600 KB Output is correct
11 Correct 46 ms 1600 KB Output is correct
12 Correct 312 ms 1712 KB Output is correct
13 Correct 320 ms 1712 KB Output is correct
14 Correct 343 ms 1876 KB Output is correct
15 Correct 467 ms 1876 KB Output is correct
16 Correct 472 ms 2020 KB Output is correct
17 Correct 478 ms 2120 KB Output is correct
18 Correct 478 ms 2220 KB Output is correct
19 Correct 512 ms 2324 KB Output is correct
20 Correct 534 ms 2420 KB Output is correct
21 Correct 473 ms 2520 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 508 KB Output isn't correct
3 Halted 0 ms 0 KB -