# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
163772 |
2019-11-15T09:05:24 Z |
Alexa2001 |
Lottery (CEOI18_lot) |
C++17 |
|
735 ms |
12484 KB |
#include <bits/stdc++.h>
using namespace std;
const int Nmax = 1e4 + 5, Qmax = 205;
int a[Nmax], match[Nmax], where[Qmax];
pair<int,int> mat[Qmax];
int n, q, l;
int ans[Nmax][Qmax];
void new_match(int x, int y, int mat)
{
ans[x][match[mat]] ++;
ans[y][match[mat]] ++;
}
void prec(int d)
{
int i, dif = 0;
for(i=1; i<=l; ++i)
dif += (a[i] != a[d+i]);
new_match(1, d+1, dif);
for(i=l+1; i+d<=n; ++i)
{
dif += (a[i] != a[i+d]);
dif -= (a[i-l] != a[i+d-l]);
new_match(i-l+1, i+d-l+1, dif);
}
}
int main()
{
// freopen("input", "r", stdin);
cin.sync_with_stdio(false); cin.tie(0);
cin >> n >> l;
int i, j;
for(i=1; i<=n; ++i) cin >> a[i];
cin >> q;
for(i=1; i<=q; ++i) cin >> mat[i].first, mat[i].second = i;
sort(mat+1, mat+q+1);
for(i=0; i<=l; ++i)
match[i] = lower_bound(mat+1, mat+q+1, make_pair(i, 0)) - mat;
for(i=1; i<=n-l; ++i)
prec(i);
for(i=1; i<=n; ++i)
for(j=1; j<=q; ++j)
ans[i][j] += ans[i][j-1];
for(i=1; i<=q; ++i) where[mat[i].second] = i;
for(i=1; i<=q; ++i)
{
for(j=1; j<=n-l+1; ++j) cout << ans[j][where[i]] << ' ';
cout << '\n';
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
380 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
504 KB |
Output is correct |
5 |
Correct |
2 ms |
504 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
3 ms |
396 KB |
Output is correct |
8 |
Correct |
3 ms |
632 KB |
Output is correct |
9 |
Correct |
3 ms |
632 KB |
Output is correct |
10 |
Correct |
3 ms |
632 KB |
Output is correct |
11 |
Correct |
3 ms |
632 KB |
Output is correct |
12 |
Correct |
3 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
380 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
504 KB |
Output is correct |
5 |
Correct |
2 ms |
504 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
3 ms |
396 KB |
Output is correct |
8 |
Correct |
3 ms |
632 KB |
Output is correct |
9 |
Correct |
3 ms |
632 KB |
Output is correct |
10 |
Correct |
3 ms |
632 KB |
Output is correct |
11 |
Correct |
3 ms |
632 KB |
Output is correct |
12 |
Correct |
3 ms |
632 KB |
Output is correct |
13 |
Correct |
24 ms |
2040 KB |
Output is correct |
14 |
Correct |
15 ms |
2040 KB |
Output is correct |
15 |
Correct |
14 ms |
2040 KB |
Output is correct |
16 |
Correct |
21 ms |
2112 KB |
Output is correct |
17 |
Correct |
19 ms |
2088 KB |
Output is correct |
18 |
Correct |
19 ms |
2040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
604 ms |
8568 KB |
Output is correct |
2 |
Correct |
622 ms |
8568 KB |
Output is correct |
3 |
Correct |
626 ms |
8488 KB |
Output is correct |
4 |
Correct |
604 ms |
8568 KB |
Output is correct |
5 |
Correct |
152 ms |
8568 KB |
Output is correct |
6 |
Correct |
518 ms |
8568 KB |
Output is correct |
7 |
Correct |
155 ms |
8568 KB |
Output is correct |
8 |
Correct |
280 ms |
8696 KB |
Output is correct |
9 |
Correct |
556 ms |
8696 KB |
Output is correct |
10 |
Correct |
611 ms |
8540 KB |
Output is correct |
11 |
Correct |
24 ms |
2808 KB |
Output is correct |
12 |
Correct |
273 ms |
7672 KB |
Output is correct |
13 |
Correct |
205 ms |
8568 KB |
Output is correct |
14 |
Correct |
207 ms |
8568 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
604 ms |
8568 KB |
Output is correct |
2 |
Correct |
622 ms |
8568 KB |
Output is correct |
3 |
Correct |
626 ms |
8488 KB |
Output is correct |
4 |
Correct |
604 ms |
8568 KB |
Output is correct |
5 |
Correct |
152 ms |
8568 KB |
Output is correct |
6 |
Correct |
518 ms |
8568 KB |
Output is correct |
7 |
Correct |
155 ms |
8568 KB |
Output is correct |
8 |
Correct |
280 ms |
8696 KB |
Output is correct |
9 |
Correct |
556 ms |
8696 KB |
Output is correct |
10 |
Correct |
611 ms |
8540 KB |
Output is correct |
11 |
Correct |
24 ms |
2808 KB |
Output is correct |
12 |
Correct |
273 ms |
7672 KB |
Output is correct |
13 |
Correct |
205 ms |
8568 KB |
Output is correct |
14 |
Correct |
207 ms |
8568 KB |
Output is correct |
15 |
Correct |
569 ms |
8464 KB |
Output is correct |
16 |
Correct |
486 ms |
8520 KB |
Output is correct |
17 |
Correct |
621 ms |
8568 KB |
Output is correct |
18 |
Correct |
609 ms |
8568 KB |
Output is correct |
19 |
Correct |
617 ms |
8696 KB |
Output is correct |
20 |
Correct |
624 ms |
8516 KB |
Output is correct |
21 |
Correct |
597 ms |
8484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
380 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
504 KB |
Output is correct |
5 |
Correct |
2 ms |
504 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
3 ms |
396 KB |
Output is correct |
8 |
Correct |
3 ms |
632 KB |
Output is correct |
9 |
Correct |
3 ms |
632 KB |
Output is correct |
10 |
Correct |
3 ms |
632 KB |
Output is correct |
11 |
Correct |
3 ms |
632 KB |
Output is correct |
12 |
Correct |
3 ms |
632 KB |
Output is correct |
13 |
Correct |
24 ms |
2040 KB |
Output is correct |
14 |
Correct |
15 ms |
2040 KB |
Output is correct |
15 |
Correct |
14 ms |
2040 KB |
Output is correct |
16 |
Correct |
21 ms |
2112 KB |
Output is correct |
17 |
Correct |
19 ms |
2088 KB |
Output is correct |
18 |
Correct |
19 ms |
2040 KB |
Output is correct |
19 |
Correct |
604 ms |
8568 KB |
Output is correct |
20 |
Correct |
622 ms |
8568 KB |
Output is correct |
21 |
Correct |
626 ms |
8488 KB |
Output is correct |
22 |
Correct |
604 ms |
8568 KB |
Output is correct |
23 |
Correct |
152 ms |
8568 KB |
Output is correct |
24 |
Correct |
518 ms |
8568 KB |
Output is correct |
25 |
Correct |
155 ms |
8568 KB |
Output is correct |
26 |
Correct |
280 ms |
8696 KB |
Output is correct |
27 |
Correct |
556 ms |
8696 KB |
Output is correct |
28 |
Correct |
611 ms |
8540 KB |
Output is correct |
29 |
Correct |
24 ms |
2808 KB |
Output is correct |
30 |
Correct |
273 ms |
7672 KB |
Output is correct |
31 |
Correct |
205 ms |
8568 KB |
Output is correct |
32 |
Correct |
207 ms |
8568 KB |
Output is correct |
33 |
Correct |
569 ms |
8464 KB |
Output is correct |
34 |
Correct |
486 ms |
8520 KB |
Output is correct |
35 |
Correct |
621 ms |
8568 KB |
Output is correct |
36 |
Correct |
609 ms |
8568 KB |
Output is correct |
37 |
Correct |
617 ms |
8696 KB |
Output is correct |
38 |
Correct |
624 ms |
8516 KB |
Output is correct |
39 |
Correct |
597 ms |
8484 KB |
Output is correct |
40 |
Correct |
603 ms |
9284 KB |
Output is correct |
41 |
Correct |
51 ms |
8696 KB |
Output is correct |
42 |
Correct |
613 ms |
9292 KB |
Output is correct |
43 |
Correct |
582 ms |
9080 KB |
Output is correct |
44 |
Correct |
593 ms |
9052 KB |
Output is correct |
45 |
Correct |
735 ms |
12372 KB |
Output is correct |
46 |
Correct |
36 ms |
8824 KB |
Output is correct |
47 |
Correct |
721 ms |
12484 KB |
Output is correct |
48 |
Correct |
721 ms |
10668 KB |
Output is correct |
49 |
Correct |
677 ms |
11256 KB |
Output is correct |