# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
482940 |
2021-10-26T22:14:18 Z |
Ozy |
Lottery (CEOI18_lot) |
C++17 |
|
2940 ms |
12340 KB |
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define MAX 10000
lli n,l,q;
lli arr[MAX+2],normal[102];
lli res[MAX+2][102];
set<lli> x;
set<lli>::iterator it;
unordered_map<lli,lli> mapa;
vector<lli> orden;
void asigna(lli pos, lli val) {
it = x.lower_bound(val);
if (*it == 1000000000000) return;
res[pos][mapa[(*it)]]++;
//debugsl(pos);
//debugsl(val);
//debug(*it);
}
void solve() {
lli val[MAX+2];
lli a;
val[0] = 0;
rep(dif,1,n-l){
rep(i,1,n-dif) {
val[i] = val[i-1];
if (arr[i] != arr[i+dif]) val[i]++;
if (i >= l) {
a = val[i] - val[i-l];
asigna(i-l+1,a);
asigna(i+dif-l+1,a);
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> l;
rep(i,1,n) cin >> arr[i];
cin >> q;
rep(i,1,q) {
cin >> normal[i];
orden.push_back(normal[i]);
}
sort(orden.begin(), orden.end());
orden.push_back(-1);
x.insert(0);
mapa[0] = 0;
rep(i,0,q-1) if(orden[i] != orden[i+1]) {
x.insert(orden[i]);
mapa[orden[i]] = i+1;
}
x.insert(1000000000000);
solve();
rep(i,1,n) {
rep(j,1,q) res[i][j] += res[i][j-1];
}
lli act;
rep(i,1,q) {
act = mapa[normal[i]];
rep(j,1,n-l+1) {
cout << res[j][act] << ' ';
}
cout << "\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
460 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
1 ms |
460 KB |
Output is correct |
5 |
Correct |
0 ms |
460 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
7 |
Correct |
1 ms |
460 KB |
Output is correct |
8 |
Correct |
1 ms |
588 KB |
Output is correct |
9 |
Correct |
1 ms |
588 KB |
Output is correct |
10 |
Correct |
3 ms |
588 KB |
Output is correct |
11 |
Correct |
1 ms |
588 KB |
Output is correct |
12 |
Correct |
3 ms |
588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
460 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
1 ms |
460 KB |
Output is correct |
5 |
Correct |
0 ms |
460 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
7 |
Correct |
1 ms |
460 KB |
Output is correct |
8 |
Correct |
1 ms |
588 KB |
Output is correct |
9 |
Correct |
1 ms |
588 KB |
Output is correct |
10 |
Correct |
3 ms |
588 KB |
Output is correct |
11 |
Correct |
1 ms |
588 KB |
Output is correct |
12 |
Correct |
3 ms |
588 KB |
Output is correct |
13 |
Correct |
80 ms |
2004 KB |
Output is correct |
14 |
Correct |
43 ms |
2000 KB |
Output is correct |
15 |
Correct |
15 ms |
2012 KB |
Output is correct |
16 |
Correct |
27 ms |
2088 KB |
Output is correct |
17 |
Correct |
22 ms |
2004 KB |
Output is correct |
18 |
Correct |
24 ms |
2044 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
828 ms |
8440 KB |
Output is correct |
2 |
Correct |
671 ms |
8464 KB |
Output is correct |
3 |
Correct |
415 ms |
8460 KB |
Output is correct |
4 |
Correct |
360 ms |
8516 KB |
Output is correct |
5 |
Correct |
155 ms |
8432 KB |
Output is correct |
6 |
Correct |
340 ms |
8544 KB |
Output is correct |
7 |
Correct |
478 ms |
8548 KB |
Output is correct |
8 |
Correct |
858 ms |
8464 KB |
Output is correct |
9 |
Correct |
427 ms |
8524 KB |
Output is correct |
10 |
Correct |
383 ms |
8516 KB |
Output is correct |
11 |
Correct |
27 ms |
2724 KB |
Output is correct |
12 |
Correct |
245 ms |
7708 KB |
Output is correct |
13 |
Correct |
194 ms |
8504 KB |
Output is correct |
14 |
Correct |
212 ms |
8516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
828 ms |
8440 KB |
Output is correct |
2 |
Correct |
671 ms |
8464 KB |
Output is correct |
3 |
Correct |
415 ms |
8460 KB |
Output is correct |
4 |
Correct |
360 ms |
8516 KB |
Output is correct |
5 |
Correct |
155 ms |
8432 KB |
Output is correct |
6 |
Correct |
340 ms |
8544 KB |
Output is correct |
7 |
Correct |
478 ms |
8548 KB |
Output is correct |
8 |
Correct |
858 ms |
8464 KB |
Output is correct |
9 |
Correct |
427 ms |
8524 KB |
Output is correct |
10 |
Correct |
383 ms |
8516 KB |
Output is correct |
11 |
Correct |
27 ms |
2724 KB |
Output is correct |
12 |
Correct |
245 ms |
7708 KB |
Output is correct |
13 |
Correct |
194 ms |
8504 KB |
Output is correct |
14 |
Correct |
212 ms |
8516 KB |
Output is correct |
15 |
Correct |
1101 ms |
8456 KB |
Output is correct |
16 |
Correct |
318 ms |
8560 KB |
Output is correct |
17 |
Correct |
420 ms |
8532 KB |
Output is correct |
18 |
Correct |
387 ms |
8516 KB |
Output is correct |
19 |
Correct |
356 ms |
8672 KB |
Output is correct |
20 |
Correct |
422 ms |
8544 KB |
Output is correct |
21 |
Correct |
356 ms |
8516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
460 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
1 ms |
460 KB |
Output is correct |
5 |
Correct |
0 ms |
460 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
7 |
Correct |
1 ms |
460 KB |
Output is correct |
8 |
Correct |
1 ms |
588 KB |
Output is correct |
9 |
Correct |
1 ms |
588 KB |
Output is correct |
10 |
Correct |
3 ms |
588 KB |
Output is correct |
11 |
Correct |
1 ms |
588 KB |
Output is correct |
12 |
Correct |
3 ms |
588 KB |
Output is correct |
13 |
Correct |
80 ms |
2004 KB |
Output is correct |
14 |
Correct |
43 ms |
2000 KB |
Output is correct |
15 |
Correct |
15 ms |
2012 KB |
Output is correct |
16 |
Correct |
27 ms |
2088 KB |
Output is correct |
17 |
Correct |
22 ms |
2004 KB |
Output is correct |
18 |
Correct |
24 ms |
2044 KB |
Output is correct |
19 |
Correct |
828 ms |
8440 KB |
Output is correct |
20 |
Correct |
671 ms |
8464 KB |
Output is correct |
21 |
Correct |
415 ms |
8460 KB |
Output is correct |
22 |
Correct |
360 ms |
8516 KB |
Output is correct |
23 |
Correct |
155 ms |
8432 KB |
Output is correct |
24 |
Correct |
340 ms |
8544 KB |
Output is correct |
25 |
Correct |
478 ms |
8548 KB |
Output is correct |
26 |
Correct |
858 ms |
8464 KB |
Output is correct |
27 |
Correct |
427 ms |
8524 KB |
Output is correct |
28 |
Correct |
383 ms |
8516 KB |
Output is correct |
29 |
Correct |
27 ms |
2724 KB |
Output is correct |
30 |
Correct |
245 ms |
7708 KB |
Output is correct |
31 |
Correct |
194 ms |
8504 KB |
Output is correct |
32 |
Correct |
212 ms |
8516 KB |
Output is correct |
33 |
Correct |
1101 ms |
8456 KB |
Output is correct |
34 |
Correct |
318 ms |
8560 KB |
Output is correct |
35 |
Correct |
420 ms |
8532 KB |
Output is correct |
36 |
Correct |
387 ms |
8516 KB |
Output is correct |
37 |
Correct |
356 ms |
8672 KB |
Output is correct |
38 |
Correct |
422 ms |
8544 KB |
Output is correct |
39 |
Correct |
356 ms |
8516 KB |
Output is correct |
40 |
Correct |
2433 ms |
9276 KB |
Output is correct |
41 |
Correct |
38 ms |
8516 KB |
Output is correct |
42 |
Correct |
842 ms |
9144 KB |
Output is correct |
43 |
Correct |
624 ms |
9056 KB |
Output is correct |
44 |
Correct |
603 ms |
8956 KB |
Output is correct |
45 |
Correct |
2940 ms |
12232 KB |
Output is correct |
46 |
Correct |
47 ms |
8772 KB |
Output is correct |
47 |
Correct |
2779 ms |
12340 KB |
Output is correct |
48 |
Correct |
1012 ms |
10604 KB |
Output is correct |
49 |
Correct |
1010 ms |
11212 KB |
Output is correct |