답안 #121463

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
121463	2019-06-26T14:22:14 Z	RockyB	Lottery (CEOI18_lot)	C++17	100 / 100	1312 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	3 ms	512 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	3 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	5 ms	768 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	512 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	3 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	5 ms	768 KB	Output is correct
13	Correct	31 ms	2296 KB	Output is correct
14	Correct	18 ms	2304 KB	Output is correct
15	Correct	17 ms	2296 KB	Output is correct
16	Correct	27 ms	2340 KB	Output is correct
17	Correct	24 ms	2296 KB	Output is correct
18	Correct	27 ms	2304 KB	Output is correct

Subtask #3

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	991 ms	9464 KB	Output is correct
2	Correct	1165 ms	9444 KB	Output is correct
3	Correct	810 ms	9184 KB	Output is correct
4	Correct	833 ms	9472 KB	Output is correct
5	Correct	263 ms	9180 KB	Output is correct
6	Correct	683 ms	9340 KB	Output is correct
7	Correct	260 ms	9316 KB	Output is correct
8	Correct	431 ms	9336 KB	Output is correct
9	Correct	728 ms	9344 KB	Output is correct
10	Correct	756 ms	9336 KB	Output is correct
11	Correct	48 ms	3068 KB	Output is correct
12	Correct	437 ms	8440 KB	Output is correct
13	Correct	381 ms	9336 KB	Output is correct
14	Correct	386 ms	9220 KB	Output is correct

Subtask #4

15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	991 ms	9464 KB	Output is correct
2	Correct	1165 ms	9444 KB	Output is correct
3	Correct	810 ms	9184 KB	Output is correct
4	Correct	833 ms	9472 KB	Output is correct
5	Correct	263 ms	9180 KB	Output is correct
6	Correct	683 ms	9340 KB	Output is correct
7	Correct	260 ms	9316 KB	Output is correct
8	Correct	431 ms	9336 KB	Output is correct
9	Correct	728 ms	9344 KB	Output is correct
10	Correct	756 ms	9336 KB	Output is correct
11	Correct	48 ms	3068 KB	Output is correct
12	Correct	437 ms	8440 KB	Output is correct
13	Correct	381 ms	9336 KB	Output is correct
14	Correct	386 ms	9220 KB	Output is correct
15	Correct	887 ms	9392 KB	Output is correct
16	Correct	693 ms	9336 KB	Output is correct
17	Correct	800 ms	9336 KB	Output is correct
18	Correct	859 ms	9348 KB	Output is correct
19	Correct	792 ms	9572 KB	Output is correct
20	Correct	776 ms	9592 KB	Output is correct
21	Correct	779 ms	9464 KB	Output is correct

Subtask #5

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	512 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	3 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	5 ms	768 KB	Output is correct
13	Correct	31 ms	2296 KB	Output is correct
14	Correct	18 ms	2304 KB	Output is correct
15	Correct	17 ms	2296 KB	Output is correct
16	Correct	27 ms	2340 KB	Output is correct
17	Correct	24 ms	2296 KB	Output is correct
18	Correct	27 ms	2304 KB	Output is correct
19	Correct	991 ms	9464 KB	Output is correct
20	Correct	1165 ms	9444 KB	Output is correct
21	Correct	810 ms	9184 KB	Output is correct
22	Correct	833 ms	9472 KB	Output is correct
23	Correct	263 ms	9180 KB	Output is correct
24	Correct	683 ms	9340 KB	Output is correct
25	Correct	260 ms	9316 KB	Output is correct
26	Correct	431 ms	9336 KB	Output is correct
27	Correct	728 ms	9344 KB	Output is correct
28	Correct	756 ms	9336 KB	Output is correct
29	Correct	48 ms	3068 KB	Output is correct
30	Correct	437 ms	8440 KB	Output is correct
31	Correct	381 ms	9336 KB	Output is correct
32	Correct	386 ms	9220 KB	Output is correct
33	Correct	887 ms	9392 KB	Output is correct
34	Correct	693 ms	9336 KB	Output is correct
35	Correct	800 ms	9336 KB	Output is correct
36	Correct	859 ms	9348 KB	Output is correct
37	Correct	792 ms	9572 KB	Output is correct
38	Correct	776 ms	9592 KB	Output is correct
39	Correct	779 ms	9464 KB	Output is correct
40	Correct	1269 ms	10136 KB	Output is correct
41	Correct	42 ms	9208 KB	Output is correct
42	Correct	815 ms	10152 KB	Output is correct
43	Correct	818 ms	9600 KB	Output is correct
44	Correct	914 ms	9848 KB	Output is correct
45	Correct	1312 ms	13204 KB	Output is correct
46	Correct	47 ms	9464 KB	Output is correct
47	Correct	818 ms	13304 KB	Output is correct
48	Correct	764 ms	11516 KB	Output is correct
49	Correct	775 ms	12124 KB	Output is correct