답안 #70196 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
70196	2018-08-22T13:18:22 Z	model_code	Lottery (CEOI18_lot)	C++17	100 / 100	1213 ms	8608 KB

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;

const int maxN = 1e4 + 10;
const int maxQ = 100;

int t[maxN];
int n, l, q;

struct Quest {
    int k, i;
    Quest(int k, int i)
    : k(k), i(i) {}
    
    bool operator<(Quest const& o) const {
        return k < o.k;
    }
};

vector<Quest> quests;
int cnt[maxN];
int ans[maxQ][maxN];
int dp[maxN];

int count_diff(int x, int y) {
    int diff = 0;
    if(x > 0 && y > 0 && t[x - 1] != t[y - 1])
        diff--;
    if(t[x + l - 1] != t[y + l - 1])
        diff++;
    if(x == 0 || y == 0) {
        for(int i = 1; i < l; ++i)
            diff += t[x + i - 1] != t[y + i - 1];
    }
    return diff;
}

void ans_quests(int x) {
    for(int i = 0; i <= l; ++i)
        cnt[i] = 0;
    for(int i = n - l; i > 0; --i)
        dp[i] = dp[i - 1] + count_diff(x, i);
    dp[0] = count_diff(x, 0);

    for(int i = 0; i < n - l + 1; ++i)
        cnt[dp[i]]++;

    int k = 0, sum = 0;
    for(Quest const& q: quests) {
        while(k <= q.k) {
            sum += cnt[k];
            k++;
        }
        ans[q.i][x] = sum - 1;
    }
}

int main() {
    assert(scanf("%d%d", &n, &l) == 2);
    for(int i = 0; i < n; ++i)
        assert(scanf("%d", t + i) == 1);

    assert(scanf("%d", &q) == 1);
    for(int k, i = 0; i < q; ++i) {
        assert(scanf("%d", &k) == 1);
        quests.emplace_back(k, i);
    }
    sort(quests.begin(), quests.end());

    for(int i = 0; i < n - l + 1; ++i)
        ans_quests(i);

    for(int i = 0; i < q; ++i) {
        for(int j = 0; j < n - l + 1; ++j)
            printf("%d ", ans[i][j]);
        puts("");
    }
}

Subtask #1
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	3 ms	468 KB	Output is correct
3	Correct	2 ms	524 KB	Output is correct
4	Correct	3 ms	524 KB	Output is correct
5	Correct	2 ms	600 KB	Output is correct
6	Correct	3 ms	600 KB	Output is correct
7	Correct	2 ms	600 KB	Output is correct
8	Correct	3 ms	600 KB	Output is correct
9	Correct	3 ms	604 KB	Output is correct
10	Correct	5 ms	716 KB	Output is correct
11	Correct	5 ms	716 KB	Output is correct
12	Correct	4 ms	716 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	3 ms	468 KB	Output is correct
3	Correct	2 ms	524 KB	Output is correct
4	Correct	3 ms	524 KB	Output is correct
5	Correct	2 ms	600 KB	Output is correct
6	Correct	3 ms	600 KB	Output is correct
7	Correct	2 ms	600 KB	Output is correct
8	Correct	3 ms	600 KB	Output is correct
9	Correct	3 ms	604 KB	Output is correct
10	Correct	5 ms	716 KB	Output is correct
11	Correct	5 ms	716 KB	Output is correct
12	Correct	4 ms	716 KB	Output is correct
13	Correct	36 ms	716 KB	Output is correct
14	Correct	23 ms	824 KB	Output is correct
15	Correct	20 ms	824 KB	Output is correct
16	Correct	29 ms	924 KB	Output is correct
17	Correct	30 ms	948 KB	Output is correct
18	Correct	29 ms	948 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1134 ms	996 KB	Output is correct
2	Correct	1159 ms	1056 KB	Output is correct
3	Correct	746 ms	1056 KB	Output is correct
4	Correct	699 ms	1056 KB	Output is correct
5	Correct	241 ms	1056 KB	Output is correct
6	Correct	667 ms	1056 KB	Output is correct
7	Correct	298 ms	1056 KB	Output is correct
8	Correct	498 ms	1056 KB	Output is correct
9	Correct	721 ms	1056 KB	Output is correct
10	Correct	732 ms	1056 KB	Output is correct
11	Correct	31 ms	1056 KB	Output is correct
12	Correct	362 ms	1056 KB	Output is correct
13	Correct	324 ms	1056 KB	Output is correct
14	Correct	285 ms	1056 KB	Output is correct

Subtask #4
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1134 ms	996 KB	Output is correct
2	Correct	1159 ms	1056 KB	Output is correct
3	Correct	746 ms	1056 KB	Output is correct
4	Correct	699 ms	1056 KB	Output is correct
5	Correct	241 ms	1056 KB	Output is correct
6	Correct	667 ms	1056 KB	Output is correct
7	Correct	298 ms	1056 KB	Output is correct
8	Correct	498 ms	1056 KB	Output is correct
9	Correct	721 ms	1056 KB	Output is correct
10	Correct	732 ms	1056 KB	Output is correct
11	Correct	31 ms	1056 KB	Output is correct
12	Correct	362 ms	1056 KB	Output is correct
13	Correct	324 ms	1056 KB	Output is correct
14	Correct	285 ms	1056 KB	Output is correct
15	Correct	669 ms	1056 KB	Output is correct
16	Correct	657 ms	1056 KB	Output is correct
17	Correct	739 ms	1056 KB	Output is correct
18	Correct	761 ms	1056 KB	Output is correct
19	Correct	738 ms	1148 KB	Output is correct
20	Correct	753 ms	1148 KB	Output is correct
21	Correct	723 ms	1148 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	3 ms	468 KB	Output is correct
3	Correct	2 ms	524 KB	Output is correct
4	Correct	3 ms	524 KB	Output is correct
5	Correct	2 ms	600 KB	Output is correct
6	Correct	3 ms	600 KB	Output is correct
7	Correct	2 ms	600 KB	Output is correct
8	Correct	3 ms	600 KB	Output is correct
9	Correct	3 ms	604 KB	Output is correct
10	Correct	5 ms	716 KB	Output is correct
11	Correct	5 ms	716 KB	Output is correct
12	Correct	4 ms	716 KB	Output is correct
13	Correct	36 ms	716 KB	Output is correct
14	Correct	23 ms	824 KB	Output is correct
15	Correct	20 ms	824 KB	Output is correct
16	Correct	29 ms	924 KB	Output is correct
17	Correct	30 ms	948 KB	Output is correct
18	Correct	29 ms	948 KB	Output is correct
19	Correct	1134 ms	996 KB	Output is correct
20	Correct	1159 ms	1056 KB	Output is correct
21	Correct	746 ms	1056 KB	Output is correct
22	Correct	699 ms	1056 KB	Output is correct
23	Correct	241 ms	1056 KB	Output is correct
24	Correct	667 ms	1056 KB	Output is correct
25	Correct	298 ms	1056 KB	Output is correct
26	Correct	498 ms	1056 KB	Output is correct
27	Correct	721 ms	1056 KB	Output is correct
28	Correct	732 ms	1056 KB	Output is correct
29	Correct	31 ms	1056 KB	Output is correct
30	Correct	362 ms	1056 KB	Output is correct
31	Correct	324 ms	1056 KB	Output is correct
32	Correct	285 ms	1056 KB	Output is correct
33	Correct	669 ms	1056 KB	Output is correct
34	Correct	657 ms	1056 KB	Output is correct
35	Correct	739 ms	1056 KB	Output is correct
36	Correct	761 ms	1056 KB	Output is correct
37	Correct	738 ms	1148 KB	Output is correct
38	Correct	753 ms	1148 KB	Output is correct
39	Correct	723 ms	1148 KB	Output is correct
40	Correct	1139 ms	2312 KB	Output is correct
41	Correct	35 ms	2312 KB	Output is correct
42	Correct	630 ms	2312 KB	Output is correct
43	Correct	735 ms	2312 KB	Output is correct
44	Correct	700 ms	2312 KB	Output is correct
45	Correct	1213 ms	8472 KB	Output is correct
46	Correct	49 ms	8472 KB	Output is correct
47	Correct	802 ms	8608 KB	Output is correct
48	Correct	821 ms	8608 KB	Output is correct
49	Correct	874 ms	8608 KB	Output is correct

답안 #70196

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