oj.uz

Submission #77976

# Submission time Handle Problem Language Result Execution time Memory
77976 2018-10-01T14:43:33 Z aminra Lottery (CEOI18_lot) C++14
0 / 100
 813 ms 632 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; j++)
			cout << n - l - ans[perm[i]][j] << " ";
		cout << "\n";
	}
}

Subtask #1
0 / 25.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 813 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 813 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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