| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 383204 |
2021-03-29T08:00:38 Z |
maximath_1 |
Lottery (CEOI18_lot) |
C++11 |
|
1362 ms |
8496 KB |
#include <stdio.h>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <numeric>
#include <queue>
#include <assert.h>
#include <map>
#include <set>
#include <limits.h>
using namespace std;
#define ll long long
#define ld long double
const int MX = 10005;
const int LG = (int)log2(MX) + 2;
const int BLOCK = 105;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
#define gc getchar//_unlocked //can't for window server
void cin(int &x){
char c = gc(); bool neg = false;
for(; c < '0'||'9' < c; c = gc())
if(c == '-') neg=true;
x = c - '0'; c = gc();
for(; '0' <= c && c <= '9'; c = gc())
x = (x << 1) + (x << 3) + (c - '0');
if(neg) x = -x;
}
int n, l, v[MX], q, que[BLOCK];
int sorted_que[BLOCK], ans[MX][BLOCK], pref[MX];
int main(){
cin(n); cin(l);
for(int i = 0; i < n; i ++)
cin(v[i]);
cin(q);
for(int i = 0; i < q; i ++)
cin(que[i]);
for(int i = 0; i < q; i ++)
sorted_que[i] = que[i];
sort(sorted_que, sorted_que + q);
sorted_que[q] = l;
for(int offset = 1; offset < n - l + 1; offset ++){
for(int j = 0; j + offset < n; j ++)
if(v[j] != v[j + offset]) pref[j] = 1;
else pref[j] = 0;
for(int j = 0; j + offset < n; j ++)
pref[j] += (j ? pref[j - 1] : 0);
for(int i = 0; i + offset < n - l + 1; i ++){
int j = i + offset;
int diff = pref[i + l - 1] - (i ? pref[i - 1] : 0);
int corres = lower_bound(sorted_que, sorted_que + q + 1, diff) - sorted_que;
ans[i][corres] ++; ans[j][corres] ++;
}
}
for(int i = 0; i < n; i ++)
for(int j = 1; j < BLOCK; j ++)
ans[i][j] += ans[i][j - 1];
for(int i = 0; i < q; i ++){
int corres = lower_bound(sorted_que, sorted_que + q + 1, que[i]) - sorted_que;
for(int j = 0; j < n - l + 1; j ++)
printf("%d ", ans[j][corres]);
printf("\n");
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
2 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
2 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
2 ms |
492 KB |
Output is correct |
| 9 |
Correct |
2 ms |
492 KB |
Output is correct |
| 10 |
Correct |
2 ms |
492 KB |
Output is correct |
| 11 |
Correct |
3 ms |
492 KB |
Output is correct |
| 12 |
Correct |
2 ms |
492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
2 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
2 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
2 ms |
492 KB |
Output is correct |
| 9 |
Correct |
2 ms |
492 KB |
Output is correct |
| 10 |
Correct |
2 ms |
492 KB |
Output is correct |
| 11 |
Correct |
3 ms |
492 KB |
Output is correct |
| 12 |
Correct |
2 ms |
492 KB |
Output is correct |
| 13 |
Correct |
29 ms |
1260 KB |
Output is correct |
| 14 |
Correct |
22 ms |
1260 KB |
Output is correct |
| 15 |
Correct |
19 ms |
1260 KB |
Output is correct |
| 16 |
Correct |
29 ms |
1388 KB |
Output is correct |
| 17 |
Correct |
31 ms |
1260 KB |
Output is correct |
| 18 |
Correct |
26 ms |
1260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
657 ms |
4588 KB |
Output is correct |
| 2 |
Correct |
597 ms |
4588 KB |
Output is correct |
| 3 |
Correct |
614 ms |
4588 KB |
Output is correct |
| 4 |
Correct |
572 ms |
4716 KB |
Output is correct |
| 5 |
Correct |
246 ms |
4716 KB |
Output is correct |
| 6 |
Correct |
530 ms |
4588 KB |
Output is correct |
| 7 |
Correct |
225 ms |
4716 KB |
Output is correct |
| 8 |
Correct |
327 ms |
4716 KB |
Output is correct |
| 9 |
Correct |
556 ms |
4588 KB |
Output is correct |
| 10 |
Correct |
598 ms |
4588 KB |
Output is correct |
| 11 |
Correct |
32 ms |
1644 KB |
Output is correct |
| 12 |
Correct |
341 ms |
4204 KB |
Output is correct |
| 13 |
Correct |
299 ms |
4716 KB |
Output is correct |
| 14 |
Correct |
313 ms |
4716 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
657 ms |
4588 KB |
Output is correct |
| 2 |
Correct |
597 ms |
4588 KB |
Output is correct |
| 3 |
Correct |
614 ms |
4588 KB |
Output is correct |
| 4 |
Correct |
572 ms |
4716 KB |
Output is correct |
| 5 |
Correct |
246 ms |
4716 KB |
Output is correct |
| 6 |
Correct |
530 ms |
4588 KB |
Output is correct |
| 7 |
Correct |
225 ms |
4716 KB |
Output is correct |
| 8 |
Correct |
327 ms |
4716 KB |
Output is correct |
| 9 |
Correct |
556 ms |
4588 KB |
Output is correct |
| 10 |
Correct |
598 ms |
4588 KB |
Output is correct |
| 11 |
Correct |
32 ms |
1644 KB |
Output is correct |
| 12 |
Correct |
341 ms |
4204 KB |
Output is correct |
| 13 |
Correct |
299 ms |
4716 KB |
Output is correct |
| 14 |
Correct |
313 ms |
4716 KB |
Output is correct |
| 15 |
Correct |
537 ms |
4588 KB |
Output is correct |
| 16 |
Correct |
504 ms |
4716 KB |
Output is correct |
| 17 |
Correct |
602 ms |
4588 KB |
Output is correct |
| 18 |
Correct |
586 ms |
4588 KB |
Output is correct |
| 19 |
Correct |
581 ms |
4600 KB |
Output is correct |
| 20 |
Correct |
625 ms |
4608 KB |
Output is correct |
| 21 |
Correct |
587 ms |
4588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
2 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
2 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
2 ms |
492 KB |
Output is correct |
| 9 |
Correct |
2 ms |
492 KB |
Output is correct |
| 10 |
Correct |
2 ms |
492 KB |
Output is correct |
| 11 |
Correct |
3 ms |
492 KB |
Output is correct |
| 12 |
Correct |
2 ms |
492 KB |
Output is correct |
| 13 |
Correct |
29 ms |
1260 KB |
Output is correct |
| 14 |
Correct |
22 ms |
1260 KB |
Output is correct |
| 15 |
Correct |
19 ms |
1260 KB |
Output is correct |
| 16 |
Correct |
29 ms |
1388 KB |
Output is correct |
| 17 |
Correct |
31 ms |
1260 KB |
Output is correct |
| 18 |
Correct |
26 ms |
1260 KB |
Output is correct |
| 19 |
Correct |
657 ms |
4588 KB |
Output is correct |
| 20 |
Correct |
597 ms |
4588 KB |
Output is correct |
| 21 |
Correct |
614 ms |
4588 KB |
Output is correct |
| 22 |
Correct |
572 ms |
4716 KB |
Output is correct |
| 23 |
Correct |
246 ms |
4716 KB |
Output is correct |
| 24 |
Correct |
530 ms |
4588 KB |
Output is correct |
| 25 |
Correct |
225 ms |
4716 KB |
Output is correct |
| 26 |
Correct |
327 ms |
4716 KB |
Output is correct |
| 27 |
Correct |
556 ms |
4588 KB |
Output is correct |
| 28 |
Correct |
598 ms |
4588 KB |
Output is correct |
| 29 |
Correct |
32 ms |
1644 KB |
Output is correct |
| 30 |
Correct |
341 ms |
4204 KB |
Output is correct |
| 31 |
Correct |
299 ms |
4716 KB |
Output is correct |
| 32 |
Correct |
313 ms |
4716 KB |
Output is correct |
| 33 |
Correct |
537 ms |
4588 KB |
Output is correct |
| 34 |
Correct |
504 ms |
4716 KB |
Output is correct |
| 35 |
Correct |
602 ms |
4588 KB |
Output is correct |
| 36 |
Correct |
586 ms |
4588 KB |
Output is correct |
| 37 |
Correct |
581 ms |
4600 KB |
Output is correct |
| 38 |
Correct |
625 ms |
4608 KB |
Output is correct |
| 39 |
Correct |
587 ms |
4588 KB |
Output is correct |
| 40 |
Correct |
818 ms |
5296 KB |
Output is correct |
| 41 |
Correct |
49 ms |
4716 KB |
Output is correct |
| 42 |
Correct |
688 ms |
5300 KB |
Output is correct |
| 43 |
Correct |
658 ms |
4972 KB |
Output is correct |
| 44 |
Correct |
661 ms |
5104 KB |
Output is correct |
| 45 |
Correct |
1362 ms |
8300 KB |
Output is correct |
| 46 |
Correct |
61 ms |
4972 KB |
Output is correct |
| 47 |
Correct |
912 ms |
8496 KB |
Output is correct |
| 48 |
Correct |
913 ms |
6764 KB |
Output is correct |
| 49 |
Correct |
968 ms |
7532 KB |
Output is correct |
