답안 #162141

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
162141	2019-11-06T16:17:16 Z	Akashi	Lottery (CEOI18_lot)	C++14	100 / 100	2982 ms	8568 KB

///better top wins
#include <bits/stdc++.h>
using namespace std;

struct query{
    int x, p;
    bool operator < (const query &aux)const{
        if(x != aux.x) return x < aux.x;
        return p < aux.p;
    }
};

query q[105];

int n, l, t;
int a[10005], f[10005];
int dp[10005][105];

void add(int p, int x){
    int st = 1, dr = t;
    while(st <= dr){
        int mij = (st + dr) / 2;

        if(q[mij].x < x) st = mij + 1;
        else dr = mij - 1;
    }

    if(q[st].x == x) ++dr;
    if(x > q[dr].x) ++dr;
    if(dr > t) return ;

    dp[p][dr] += 1;
}

int main()
{
//    freopen("1.in", "r", stdin);

    scanf("%d%d", &n, &l);

    for(int i = 1; i <= n ; ++i)
        scanf("%d", &a[i]);

    scanf("%d", &t);
    for(int i = 1; i <= t ; ++i){
        scanf("%d", &q[i].x);
        q[i].p = i;
    }

    sort(q + 1, q + t + 1);

    for(int start = 2; start <= n - l + 1 ; ++start){

        int i = 1, j = start, dif = 0;
        for(int t = 1; t <= l ; ++t, ++i, ++j) if(a[i] != a[j]) ++dif;

        add(1, dif);
        add(start, dif);

        while(j <= n){

            if(a[i - l] != a[j - l]) --dif;
            if(a[i] != a[j]) ++dif;

            add(i - l + 1, dif);
            add(j - l + 1, dif);

            ++i; ++j;
        }
    }

    for(int i = 1; i <= t ; ++i) f[q[i].p] = i;

    for(int i = 1; i <= n - l + 1 ; ++i){
        for(int j = 1; j <= t ; ++j)
            dp[i][j] += dp[i][j - 1];
    }

    for(int i = 1; i <= t ; ++i){
        for(int j = 1; j <= n - l + 1 ; ++j)
            printf("%d ", dp[j][f[i]]);
        printf("\n");
    }

    return 0;
}

Compilation message

lot.cpp: In function 'int main()':
lot.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &l);
     ~~~~~^~~~~~~~~~~~~~~~
lot.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~
lot.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &t);
     ~~~~~^~~~~~~~~~
lot.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &q[i].x);
         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	380 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	3 ms	376 KB	Output is correct
9	Correct	3 ms	376 KB	Output is correct
10	Correct	4 ms	504 KB	Output is correct
11	Correct	3 ms	504 KB	Output is correct
12	Correct	4 ms	504 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	380 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	3 ms	376 KB	Output is correct
9	Correct	3 ms	376 KB	Output is correct
10	Correct	4 ms	504 KB	Output is correct
11	Correct	3 ms	504 KB	Output is correct
12	Correct	4 ms	504 KB	Output is correct
13	Correct	55 ms	1208 KB	Output is correct
14	Correct	63 ms	1016 KB	Output is correct
15	Correct	23 ms	1016 KB	Output is correct
16	Correct	53 ms	1144 KB	Output is correct
17	Correct	38 ms	1144 KB	Output is correct
18	Correct	38 ms	1144 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	949 ms	4508 KB	Output is correct
2	Correct	1179 ms	4512 KB	Output is correct
3	Correct	661 ms	4672 KB	Output is correct
4	Correct	579 ms	4484 KB	Output is correct
5	Correct	180 ms	2424 KB	Output is correct
6	Correct	518 ms	4216 KB	Output is correct
7	Correct	256 ms	2424 KB	Output is correct
8	Correct	503 ms	3320 KB	Output is correct
9	Correct	569 ms	4364 KB	Output is correct
10	Correct	766 ms	4600 KB	Output is correct
11	Correct	45 ms	1144 KB	Output is correct
12	Correct	356 ms	3220 KB	Output is correct
13	Correct	238 ms	2808 KB	Output is correct
14	Correct	254 ms	2936 KB	Output is correct

Subtask #4
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	949 ms	4508 KB	Output is correct
2	Correct	1179 ms	4512 KB	Output is correct
3	Correct	661 ms	4672 KB	Output is correct
4	Correct	579 ms	4484 KB	Output is correct
5	Correct	180 ms	2424 KB	Output is correct
6	Correct	518 ms	4216 KB	Output is correct
7	Correct	256 ms	2424 KB	Output is correct
8	Correct	503 ms	3320 KB	Output is correct
9	Correct	569 ms	4364 KB	Output is correct
10	Correct	766 ms	4600 KB	Output is correct
11	Correct	45 ms	1144 KB	Output is correct
12	Correct	356 ms	3220 KB	Output is correct
13	Correct	238 ms	2808 KB	Output is correct
14	Correct	254 ms	2936 KB	Output is correct
15	Correct	900 ms	4376 KB	Output is correct
16	Correct	493 ms	4216 KB	Output is correct
17	Correct	669 ms	4628 KB	Output is correct
18	Correct	581 ms	4600 KB	Output is correct
19	Correct	698 ms	4652 KB	Output is correct
20	Correct	584 ms	4564 KB	Output is correct
21	Correct	581 ms	4700 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	380 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	3 ms	376 KB	Output is correct
9	Correct	3 ms	376 KB	Output is correct
10	Correct	4 ms	504 KB	Output is correct
11	Correct	3 ms	504 KB	Output is correct
12	Correct	4 ms	504 KB	Output is correct
13	Correct	55 ms	1208 KB	Output is correct
14	Correct	63 ms	1016 KB	Output is correct
15	Correct	23 ms	1016 KB	Output is correct
16	Correct	53 ms	1144 KB	Output is correct
17	Correct	38 ms	1144 KB	Output is correct
18	Correct	38 ms	1144 KB	Output is correct
19	Correct	949 ms	4508 KB	Output is correct
20	Correct	1179 ms	4512 KB	Output is correct
21	Correct	661 ms	4672 KB	Output is correct
22	Correct	579 ms	4484 KB	Output is correct
23	Correct	180 ms	2424 KB	Output is correct
24	Correct	518 ms	4216 KB	Output is correct
25	Correct	256 ms	2424 KB	Output is correct
26	Correct	503 ms	3320 KB	Output is correct
27	Correct	569 ms	4364 KB	Output is correct
28	Correct	766 ms	4600 KB	Output is correct
29	Correct	45 ms	1144 KB	Output is correct
30	Correct	356 ms	3220 KB	Output is correct
31	Correct	238 ms	2808 KB	Output is correct
32	Correct	254 ms	2936 KB	Output is correct
33	Correct	900 ms	4376 KB	Output is correct
34	Correct	493 ms	4216 KB	Output is correct
35	Correct	669 ms	4628 KB	Output is correct
36	Correct	581 ms	4600 KB	Output is correct
37	Correct	698 ms	4652 KB	Output is correct
38	Correct	584 ms	4564 KB	Output is correct
39	Correct	581 ms	4700 KB	Output is correct
40	Correct	2160 ms	5288 KB	Output is correct
41	Correct	24 ms	1016 KB	Output is correct
42	Correct	1219 ms	5272 KB	Output is correct
43	Correct	1051 ms	4856 KB	Output is correct
44	Correct	1050 ms	4984 KB	Output is correct
45	Correct	2982 ms	8440 KB	Output is correct
46	Correct	34 ms	1144 KB	Output is correct
47	Correct	2714 ms	8568 KB	Output is correct
48	Correct	1403 ms	6596 KB	Output is correct
49	Correct	1416 ms	7156 KB	Output is correct

답안 #162141

Compilation message

Subtask #1 25.0 / 25.0

Subtask #2 20.0 / 20.0

Subtask #3 20.0 / 20.0

Subtask #4 15.0 / 15.0

Subtask #5 20.0 / 20.0

Subtask #1
25.0 / 25.0

Subtask #2
20.0 / 20.0

Subtask #3
20.0 / 20.0

Subtask #4
15.0 / 15.0

Subtask #5
20.0 / 20.0