# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
259984 | Kenzo_1114 | Lottery (CEOI18_lot) | C++17 | 611 ms | 8312 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 10010;
const int MAXQ = 110;
int N, L, Q, q[MAXN], a[MAXN], ans[MAXQ][MAXN], K[MAXN];
int main ()
{
scanf("%d %d", &N, &L);
for(int i = 1; i <= N; i++) scanf("%d", &a[i]);
scanf("%d", &Q);
vector<pair<int, int> > qry;
for(int i = 0, k; i < Q; i++)
{
scanf("%d", &k);
qry.push_back(make_pair(k, i));
}
sort(qry.begin(), qry.end());
for(int i = 0; i < Q; i++) q[qry[i].second] = i;
for(int k = 0, id = 0; k <= L; k++)
{
while(k > qry[id].first && id < qry.size()) id++;
K[k] = id;
}
for(int j = 1; j + L <= N; j++)
{
int k = 0;
for(int i = 1; i <= L; i++) k += (a[i] != a[i + j]);
ans[K[k]][1]++;
ans[K[k]][1 + j]++;
// printf("(1, %d) = %d\n", 1 + j, k);
for(int i = 2; i + j + L - 1 <= N; i++)
{
k -= (a[i - 1] != a[i + j - 1]);
k += (a[i + L - 1] != a[i + j + L - 1]);
// printf("(%d, %d) = %d\n", i, i + j, k);
ans[K[k]][i]++;
ans[K[k]][i + j]++;
}
}
for(int i = 1; i < Q; i++)
for(int j = 1; j <= N; j++)
ans[i][j] += ans[i - 1][j];
for(int i = 0; i < Q; i++)
{
for(int j = 1; j + L - 1 <= N; j++) printf("%d ", ans[q[i]][j]);
printf("\n");
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |