답안 #70197 :: oj.uz

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

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
	int n, l, q;
	vector<int> tab;
	cin >> n >> l;
	tab.resize(n);
	for (int i = 0; i < n; i ++) cin >> tab[i];
	cin >> q;
	vector<pair<int,int>> que;
	for (int i = 0; i < q; i ++) {
		int x;
		cin >> x;
		que.emplace_back(x, i);
	}
	vector<vector<short int>> res(n, vector<short int>(q + 1));
	sort(que.begin(), que.end());
	for (int diff = 1; diff + l <= n; diff ++) {
		int sum = 0;
        int gdzie = q;
		for (int i = 0; i + diff < n; i ++) {
            int delta = 0;
			delta = (tab[i] == tab[i + diff]);
			if (i - l >= 0) {
				delta -= (tab[i - l] == tab[i - l + diff]);
			}
            sum += delta;
            if (i - l + 1 > 0) {
                if (delta > 0) {
                    while (gdzie > 0 && que[gdzie - 1].first >= l - sum) {
                        gdzie --;
                    }
                }
                if (delta < 0) {
                    while (gdzie < q && que[gdzie].first < l - sum) {
                        gdzie ++;
                    }
                }
                if (gdzie == q) continue;
                res[i - l + 1][q] ++;
                res[i - l + 1 + diff][q] ++;
                if (gdzie) {
                    res[i - l + 1][gdzie - 1] --;
                    res[i - l + 1 + diff][gdzie - 1] --;
                }
            } else if (i - l + 1 == 0) {
                while (gdzie > 0 && que[gdzie - 1].first >= l - sum) gdzie --;
                while (gdzie < q && que[gdzie].first < l - sum) gdzie ++;
                if (gdzie == q) continue;
                res[i - l + 1][q] ++;
                res[i - l + 1 + diff][q] ++;
                if (gdzie) {
                    res[i - l + 1][gdzie - 1] --;
                    res[i - l + 1 + diff][gdzie - 1] --;
                }
            }
		}
	}
    for (int j = q - 1; j >= 0; j--)
        for (int i = 0; i <= n - l; i ++)
            res[i][j] += res[i][j + 1];
    for (int i = 0; i < q; i ++) {
        for (int k = 0; k < q; k ++) {
            if (que[k].second == i) {
                for (int j = 0; j <= n - l; j ++) {
                    cout << res[j][k] << " ";
                }
            }
        }
        cout << "\n";
    }
}

Subtask #1
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	3 ms	356 KB	Output is correct
3	Correct	3 ms	436 KB	Output is correct
4	Correct	3 ms	436 KB	Output is correct
5	Correct	3 ms	508 KB	Output is correct
6	Correct	2 ms	508 KB	Output is correct
7	Correct	3 ms	544 KB	Output is correct
8	Correct	3 ms	672 KB	Output is correct
9	Correct	4 ms	672 KB	Output is correct
10	Correct	3 ms	672 KB	Output is correct
11	Correct	3 ms	672 KB	Output is correct
12	Correct	3 ms	672 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	3 ms	356 KB	Output is correct
3	Correct	3 ms	436 KB	Output is correct
4	Correct	3 ms	436 KB	Output is correct
5	Correct	3 ms	508 KB	Output is correct
6	Correct	2 ms	508 KB	Output is correct
7	Correct	3 ms	544 KB	Output is correct
8	Correct	3 ms	672 KB	Output is correct
9	Correct	4 ms	672 KB	Output is correct
10	Correct	3 ms	672 KB	Output is correct
11	Correct	3 ms	672 KB	Output is correct
12	Correct	3 ms	672 KB	Output is correct
13	Correct	24 ms	780 KB	Output is correct
14	Correct	20 ms	908 KB	Output is correct
15	Correct	10 ms	908 KB	Output is correct
16	Correct	13 ms	928 KB	Output is correct
17	Correct	14 ms	928 KB	Output is correct
18	Correct	13 ms	928 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	621 ms	1276 KB	Output is correct
2	Correct	567 ms	1280 KB	Output is correct
3	Correct	266 ms	1296 KB	Output is correct
4	Correct	203 ms	1296 KB	Output is correct
5	Correct	104 ms	1296 KB	Output is correct
6	Correct	186 ms	1296 KB	Output is correct
7	Correct	130 ms	1324 KB	Output is correct
8	Correct	217 ms	1324 KB	Output is correct
9	Correct	220 ms	1324 KB	Output is correct
10	Correct	208 ms	1324 KB	Output is correct
11	Correct	19 ms	1324 KB	Output is correct
12	Correct	171 ms	1324 KB	Output is correct
13	Correct	119 ms	1324 KB	Output is correct
14	Correct	126 ms	1324 KB	Output is correct

Subtask #4
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	621 ms	1276 KB	Output is correct
2	Correct	567 ms	1280 KB	Output is correct
3	Correct	266 ms	1296 KB	Output is correct
4	Correct	203 ms	1296 KB	Output is correct
5	Correct	104 ms	1296 KB	Output is correct
6	Correct	186 ms	1296 KB	Output is correct
7	Correct	130 ms	1324 KB	Output is correct
8	Correct	217 ms	1324 KB	Output is correct
9	Correct	220 ms	1324 KB	Output is correct
10	Correct	208 ms	1324 KB	Output is correct
11	Correct	19 ms	1324 KB	Output is correct
12	Correct	171 ms	1324 KB	Output is correct
13	Correct	119 ms	1324 KB	Output is correct
14	Correct	126 ms	1324 KB	Output is correct
15	Correct	393 ms	1324 KB	Output is correct
16	Correct	190 ms	1324 KB	Output is correct
17	Correct	241 ms	1324 KB	Output is correct
18	Correct	193 ms	1340 KB	Output is correct
19	Correct	193 ms	1340 KB	Output is correct
20	Correct	208 ms	1340 KB	Output is correct
21	Correct	199 ms	1340 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	3 ms	356 KB	Output is correct
3	Correct	3 ms	436 KB	Output is correct
4	Correct	3 ms	436 KB	Output is correct
5	Correct	3 ms	508 KB	Output is correct
6	Correct	2 ms	508 KB	Output is correct
7	Correct	3 ms	544 KB	Output is correct
8	Correct	3 ms	672 KB	Output is correct
9	Correct	4 ms	672 KB	Output is correct
10	Correct	3 ms	672 KB	Output is correct
11	Correct	3 ms	672 KB	Output is correct
12	Correct	3 ms	672 KB	Output is correct
13	Correct	24 ms	780 KB	Output is correct
14	Correct	20 ms	908 KB	Output is correct
15	Correct	10 ms	908 KB	Output is correct
16	Correct	13 ms	928 KB	Output is correct
17	Correct	14 ms	928 KB	Output is correct
18	Correct	13 ms	928 KB	Output is correct
19	Correct	621 ms	1276 KB	Output is correct
20	Correct	567 ms	1280 KB	Output is correct
21	Correct	266 ms	1296 KB	Output is correct
22	Correct	203 ms	1296 KB	Output is correct
23	Correct	104 ms	1296 KB	Output is correct
24	Correct	186 ms	1296 KB	Output is correct
25	Correct	130 ms	1324 KB	Output is correct
26	Correct	217 ms	1324 KB	Output is correct
27	Correct	220 ms	1324 KB	Output is correct
28	Correct	208 ms	1324 KB	Output is correct
29	Correct	19 ms	1324 KB	Output is correct
30	Correct	171 ms	1324 KB	Output is correct
31	Correct	119 ms	1324 KB	Output is correct
32	Correct	126 ms	1324 KB	Output is correct
33	Correct	393 ms	1324 KB	Output is correct
34	Correct	190 ms	1324 KB	Output is correct
35	Correct	241 ms	1324 KB	Output is correct
36	Correct	193 ms	1340 KB	Output is correct
37	Correct	193 ms	1340 KB	Output is correct
38	Correct	208 ms	1340 KB	Output is correct
39	Correct	199 ms	1340 KB	Output is correct
40	Correct	779 ms	2388 KB	Output is correct
41	Correct	26 ms	2388 KB	Output is correct
42	Correct	249 ms	2388 KB	Output is correct
43	Correct	212 ms	2388 KB	Output is correct
44	Correct	197 ms	2388 KB	Output is correct
45	Correct	1223 ms	6900 KB	Output is correct
46	Correct	51 ms	6900 KB	Output is correct
47	Correct	815 ms	7032 KB	Output is correct
48	Correct	281 ms	7032 KB	Output is correct
49	Correct	259 ms	7032 KB	Output is correct

답안 #70197

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