답안 #538251

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
538251	2022-03-16T11:59:03 Z	alextodoran	Lottery (CEOI18_lot)	C++17	100 / 100	1709 ms	29564 KB

lot

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 10000;
const int Q_MAX = 100;
const int B = 1200;

int n, len;
int a[N_MAX + 2];
int q;
int k[Q_MAX + 2];

int qord[Q_MAX + 2];
int qid[N_MAX + 2];

short int sim[N_MAX + 2][B + 2];
short int pref[N_MAX + 2][Q_MAX + 2];

void solve (int l, int r) {
    for (int x = 1; x <= n - len + 1; x++) {
        for (int y = 1; y <= r - l + 1; y++) {
            sim[x][y] = 0;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = l; j <= r + len - 1; j++) {
            if (a[i] != a[j]) {
                int x1 = i - len + 1, y1 = j - len + 1;
                int x2 = i, y2 = j;
                int out1 = max({0, 1 - x1, l - y1});
                int out2 = max({0, x2 - (n - len + 1), y2 - r});
                x1 += out1; y1 += out1;
                x2 -= out2; y2 -= out2;
                if (x1 > x2 || y1 > y2) {
                    continue;
                }
                sim[x1][y1 - l + 1]++;
                sim[x2 + 1][(y2 + 1) - l + 1]--;
            }
        }
    }
    for (int x = 1; x <= n - len + 1; x++) {
        for (int y = 1; y <= r - l + 1; y++) {
            sim[x][y] += sim[x - 1][y - 1];
            pref[x][qid[sim[x][y]]]++;
        }
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> len;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    cin >> q;
    for (int i = 1; i <= q; i++) {
        cin >> k[i];
        qord[i] = i;
    }
    sort(qord + 1, qord + q + 1, [&] (const int &i, const int &j) {
        return k[i] < k[j];
    });
    for (int s = len, i = q + 1; s >= 0; s--) {
        while (i > 1 && k[qord[i - 1]] >= s) {
            i--;
        }
        qid[s] = i;
    }

    for (int i = 1; (i - 1) * B + 1 <= n - len + 1; i++) {
        solve((i - 1) * B + 1, min(i * B, n - len + 1));
    }
    for (int x = 1; x <= n - len + 1; x++) {
        for (int i = 1; i <= q; i++) {
            pref[x][i] += pref[x][i - 1];
        }
    }

    for (int i = 1; i <= q; i++) {
        for (int x = 1; x <= n - len + 1; x++) {
            cout << pref[x][qid[k[i]]] - 1 << " ";
        }
        cout << "\n";
    }

    return 0;
}

Subtask #1

25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	468 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	468 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	0 ms	468 KB	Output is correct
8	Correct	1 ms	724 KB	Output is correct
9	Correct	1 ms	724 KB	Output is correct
10	Correct	2 ms	980 KB	Output is correct
11	Correct	2 ms	980 KB	Output is correct
12	Correct	2 ms	980 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	468 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	468 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	0 ms	468 KB	Output is correct
8	Correct	1 ms	724 KB	Output is correct
9	Correct	1 ms	724 KB	Output is correct
10	Correct	2 ms	980 KB	Output is correct
11	Correct	2 ms	980 KB	Output is correct
12	Correct	2 ms	980 KB	Output is correct
13	Correct	46 ms	5436 KB	Output is correct
14	Correct	39 ms	3748 KB	Output is correct
15	Correct	40 ms	3744 KB	Output is correct
16	Correct	46 ms	4920 KB	Output is correct
17	Correct	44 ms	4612 KB	Output is correct
18	Correct	48 ms	4652 KB	Output is correct

Subtask #3

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	980 ms	25868 KB	Output is correct
2	Correct	988 ms	25860 KB	Output is correct
3	Correct	1151 ms	25868 KB	Output is correct
4	Correct	1217 ms	25336 KB	Output is correct
5	Correct	1235 ms	13148 KB	Output is correct
6	Correct	1324 ms	24100 KB	Output is correct
7	Correct	387 ms	13236 KB	Output is correct
8	Correct	489 ms	18232 KB	Output is correct
9	Correct	1224 ms	25048 KB	Output is correct
10	Correct	1171 ms	25484 KB	Output is correct
11	Correct	76 ms	5388 KB	Output is correct
12	Correct	1068 ms	18008 KB	Output is correct
13	Correct	1709 ms	15444 KB	Output is correct
14	Correct	1513 ms	15532 KB	Output is correct

Subtask #4

15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	980 ms	25868 KB	Output is correct
2	Correct	988 ms	25860 KB	Output is correct
3	Correct	1151 ms	25868 KB	Output is correct
4	Correct	1217 ms	25336 KB	Output is correct
5	Correct	1235 ms	13148 KB	Output is correct
6	Correct	1324 ms	24100 KB	Output is correct
7	Correct	387 ms	13236 KB	Output is correct
8	Correct	489 ms	18232 KB	Output is correct
9	Correct	1224 ms	25048 KB	Output is correct
10	Correct	1171 ms	25484 KB	Output is correct
11	Correct	76 ms	5388 KB	Output is correct
12	Correct	1068 ms	18008 KB	Output is correct
13	Correct	1709 ms	15444 KB	Output is correct
14	Correct	1513 ms	15532 KB	Output is correct
15	Correct	1283 ms	25024 KB	Output is correct
16	Correct	1398 ms	23336 KB	Output is correct
17	Correct	1103 ms	25836 KB	Output is correct
18	Correct	1169 ms	25684 KB	Output is correct
19	Correct	1194 ms	25608 KB	Output is correct
20	Correct	1175 ms	25564 KB	Output is correct
21	Correct	1162 ms	25624 KB	Output is correct

Subtask #5

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	468 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	468 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	0 ms	468 KB	Output is correct
8	Correct	1 ms	724 KB	Output is correct
9	Correct	1 ms	724 KB	Output is correct
10	Correct	2 ms	980 KB	Output is correct
11	Correct	2 ms	980 KB	Output is correct
12	Correct	2 ms	980 KB	Output is correct
13	Correct	46 ms	5436 KB	Output is correct
14	Correct	39 ms	3748 KB	Output is correct
15	Correct	40 ms	3744 KB	Output is correct
16	Correct	46 ms	4920 KB	Output is correct
17	Correct	44 ms	4612 KB	Output is correct
18	Correct	48 ms	4652 KB	Output is correct
19	Correct	980 ms	25868 KB	Output is correct
20	Correct	988 ms	25860 KB	Output is correct
21	Correct	1151 ms	25868 KB	Output is correct
22	Correct	1217 ms	25336 KB	Output is correct
23	Correct	1235 ms	13148 KB	Output is correct
24	Correct	1324 ms	24100 KB	Output is correct
25	Correct	387 ms	13236 KB	Output is correct
26	Correct	489 ms	18232 KB	Output is correct
27	Correct	1224 ms	25048 KB	Output is correct
28	Correct	1171 ms	25484 KB	Output is correct
29	Correct	76 ms	5388 KB	Output is correct
30	Correct	1068 ms	18008 KB	Output is correct
31	Correct	1709 ms	15444 KB	Output is correct
32	Correct	1513 ms	15532 KB	Output is correct
33	Correct	1283 ms	25024 KB	Output is correct
34	Correct	1398 ms	23336 KB	Output is correct
35	Correct	1103 ms	25836 KB	Output is correct
36	Correct	1169 ms	25684 KB	Output is correct
37	Correct	1194 ms	25608 KB	Output is correct
38	Correct	1175 ms	25564 KB	Output is correct
39	Correct	1162 ms	25624 KB	Output is correct
40	Correct	991 ms	26456 KB	Output is correct
41	Correct	244 ms	3020 KB	Output is correct
42	Correct	1144 ms	26332 KB	Output is correct
43	Correct	1262 ms	25128 KB	Output is correct
44	Correct	1272 ms	25256 KB	Output is correct
45	Correct	1078 ms	29456 KB	Output is correct
46	Correct	256 ms	3372 KB	Output is correct
47	Correct	1185 ms	29564 KB	Output is correct
48	Correct	1334 ms	26900 KB	Output is correct
49	Correct	1313 ms	27540 KB	Output is correct