답안 #121461

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
121461	2019-06-26T14:21:21 Z	RockyB	Lottery (CEOI18_lot)	C++17	100 / 100	1380 ms	13304 KB

lot

/// In The Name Of God

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>

#define f first
#define s second

#define pb push_back
#define pp pop_back
#define mp make_pair

#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()

#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, l, r) for (int i = (l); i >= (r); i--)

#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

#define nl '\n'
#define ioi exit(0);

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int N = (int)2e4 + 7;
const int inf = (int)1e9 + 7;
const int mod = (int)1e9 + 7;
const ll linf = (ll)1e18 + 7;

const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};

using namespace std;

int n, q, l;
int a[N];

int cnt1[N], cnt2[N];
pair <int, int> k[N];
int pref[N][110], ans[N][110];

int dp[N];
int get(int val) {
	if (~dp[val]) return dp[val];
	int pos = lower_bound (k + 1, k + 1 + q, mp(val, -inf)) - k;
	if (pos > q + 1) ioi
	return dp[val] = pos;
}
int main() {
	#ifdef IOI2018
		freopen ("in.txt", "r", stdin);
		freopen ("slow.out", "w", stdout);
	#endif
	Kazakhstan
	cin >> n >> l;
	rep(i, 1, n) cin >> a[i];
	cin >> q;	
	rep(i, 1, q) {
		cin >> k[i].f;
		k[i].s = i;
	}
	sort (k + 1, k + 1 + q);
	memset(dp, -1, sizeof(dp));
	rep(d, 1, n - l) {
		int l1 = 1, l2 = 1 + d, df = 0;
		rep(i, 1, n) {
			if (a[i] != a[i + d]) ++df;
			while (i - l1 + 1 > l) {
				if (a[l1] != a[l2]) --df;
				l1++, l2++;
			}
			if (i >= l) {
				cnt1[l1] = df;
				cnt2[l2] = df;
			}
		}
		rep(i, 1, n) {
			if (i + d + l - 1 <= n) { 
				int pos = get(cnt1[i]);
				//cerr << i << ' ' << cnt1[i] << ' ' << pos << nl;
				pref[i][pos]++;
			}
			if (i + l - 1 <= n && i - d > 0) {
				int pos = get(cnt2[i]);
				pref[i][pos]++;
			}
		}
		//cout << nl;
	}
	rep(i, 1, n) {
		rep(j, 1, q) {
			pref[i][j] += pref[i][j - 1];
			ans[i][k[j].s] = pref[i][j];
		}
	}
	rep(i, 1, q) {
		rep(j, 1, n - l + 1) {
			cout << ans[j][i] << ' ';
		}
		cout << nl;
	}
	ioi
}

Subtask #1

25.0 / 25.0

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

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	512 KB	Output is correct
3	Correct	2 ms	512 KB	Output is correct
4	Correct	2 ms	512 KB	Output is correct
5	Correct	2 ms	512 KB	Output is correct
6	Correct	2 ms	512 KB	Output is correct
7	Correct	2 ms	512 KB	Output is correct
8	Correct	3 ms	768 KB	Output is correct
9	Correct	2 ms	768 KB	Output is correct
10	Correct	3 ms	768 KB	Output is correct
11	Correct	3 ms	768 KB	Output is correct
12	Correct	3 ms	768 KB	Output is correct
13	Correct	32 ms	2168 KB	Output is correct
14	Correct	19 ms	2304 KB	Output is correct
15	Correct	18 ms	2176 KB	Output is correct
16	Correct	28 ms	2296 KB	Output is correct
17	Correct	26 ms	2296 KB	Output is correct
18	Correct	25 ms	2304 KB	Output is correct

Subtask #3

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1083 ms	9412 KB	Output is correct
2	Correct	1257 ms	9336 KB	Output is correct
3	Correct	987 ms	9548 KB	Output is correct
4	Correct	893 ms	9464 KB	Output is correct
5	Correct	260 ms	9244 KB	Output is correct
6	Correct	757 ms	9468 KB	Output is correct
7	Correct	258 ms	9208 KB	Output is correct
8	Correct	472 ms	9452 KB	Output is correct
9	Correct	787 ms	9384 KB	Output is correct
10	Correct	824 ms	9464 KB	Output is correct
11	Correct	43 ms	3064 KB	Output is correct
12	Correct	471 ms	8412 KB	Output is correct
13	Correct	351 ms	9340 KB	Output is correct
14	Correct	360 ms	9252 KB	Output is correct

Subtask #4

15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1083 ms	9412 KB	Output is correct
2	Correct	1257 ms	9336 KB	Output is correct
3	Correct	987 ms	9548 KB	Output is correct
4	Correct	893 ms	9464 KB	Output is correct
5	Correct	260 ms	9244 KB	Output is correct
6	Correct	757 ms	9468 KB	Output is correct
7	Correct	258 ms	9208 KB	Output is correct
8	Correct	472 ms	9452 KB	Output is correct
9	Correct	787 ms	9384 KB	Output is correct
10	Correct	824 ms	9464 KB	Output is correct
11	Correct	43 ms	3064 KB	Output is correct
12	Correct	471 ms	8412 KB	Output is correct
13	Correct	351 ms	9340 KB	Output is correct
14	Correct	360 ms	9252 KB	Output is correct
15	Correct	931 ms	9352 KB	Output is correct
16	Correct	733 ms	9464 KB	Output is correct
17	Correct	897 ms	9624 KB	Output is correct
18	Correct	825 ms	9468 KB	Output is correct
19	Correct	868 ms	9340 KB	Output is correct
20	Correct	826 ms	9592 KB	Output is correct
21	Correct	864 ms	9464 KB	Output is correct

Subtask #5

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	512 KB	Output is correct
3	Correct	2 ms	512 KB	Output is correct
4	Correct	2 ms	512 KB	Output is correct
5	Correct	2 ms	512 KB	Output is correct
6	Correct	2 ms	512 KB	Output is correct
7	Correct	2 ms	512 KB	Output is correct
8	Correct	3 ms	768 KB	Output is correct
9	Correct	2 ms	768 KB	Output is correct
10	Correct	3 ms	768 KB	Output is correct
11	Correct	3 ms	768 KB	Output is correct
12	Correct	3 ms	768 KB	Output is correct
13	Correct	32 ms	2168 KB	Output is correct
14	Correct	19 ms	2304 KB	Output is correct
15	Correct	18 ms	2176 KB	Output is correct
16	Correct	28 ms	2296 KB	Output is correct
17	Correct	26 ms	2296 KB	Output is correct
18	Correct	25 ms	2304 KB	Output is correct
19	Correct	1083 ms	9412 KB	Output is correct
20	Correct	1257 ms	9336 KB	Output is correct
21	Correct	987 ms	9548 KB	Output is correct
22	Correct	893 ms	9464 KB	Output is correct
23	Correct	260 ms	9244 KB	Output is correct
24	Correct	757 ms	9468 KB	Output is correct
25	Correct	258 ms	9208 KB	Output is correct
26	Correct	472 ms	9452 KB	Output is correct
27	Correct	787 ms	9384 KB	Output is correct
28	Correct	824 ms	9464 KB	Output is correct
29	Correct	43 ms	3064 KB	Output is correct
30	Correct	471 ms	8412 KB	Output is correct
31	Correct	351 ms	9340 KB	Output is correct
32	Correct	360 ms	9252 KB	Output is correct
33	Correct	931 ms	9352 KB	Output is correct
34	Correct	733 ms	9464 KB	Output is correct
35	Correct	897 ms	9624 KB	Output is correct
36	Correct	825 ms	9468 KB	Output is correct
37	Correct	868 ms	9340 KB	Output is correct
38	Correct	826 ms	9592 KB	Output is correct
39	Correct	864 ms	9464 KB	Output is correct
40	Correct	1287 ms	10280 KB	Output is correct
41	Correct	39 ms	9336 KB	Output is correct
42	Correct	870 ms	10204 KB	Output is correct
43	Correct	790 ms	9940 KB	Output is correct
44	Correct	806 ms	9976 KB	Output is correct
45	Correct	1380 ms	13176 KB	Output is correct
46	Correct	43 ms	9464 KB	Output is correct
47	Correct	885 ms	13304 KB	Output is correct
48	Correct	862 ms	11516 KB	Output is correct
49	Correct	848 ms	12156 KB	Output is correct