답안 #121467

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
121467	2019-06-26T14:23:24 Z	RockyB	Lottery (CEOI18_lot)	C++17	100 / 100	1296 ms	13104 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];
inline 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	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	2 ms	640 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	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	2 ms	640 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	28 ms	2276 KB	Output is correct
14	Correct	17 ms	2296 KB	Output is correct
15	Correct	17 ms	2268 KB	Output is correct
16	Correct	31 ms	2428 KB	Output is correct
17	Correct	23 ms	2220 KB	Output is correct
18	Correct	23 ms	2296 KB	Output is correct

Subtask #3

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	967 ms	9272 KB	Output is correct
2	Correct	1148 ms	9304 KB	Output is correct
3	Correct	789 ms	9320 KB	Output is correct
4	Correct	698 ms	9284 KB	Output is correct
5	Correct	252 ms	9224 KB	Output is correct
6	Correct	628 ms	9292 KB	Output is correct
7	Correct	255 ms	9192 KB	Output is correct
8	Correct	407 ms	9296 KB	Output is correct
9	Correct	693 ms	9344 KB	Output is correct
10	Correct	704 ms	9264 KB	Output is correct
11	Correct	37 ms	3080 KB	Output is correct
12	Correct	422 ms	8508 KB	Output is correct
13	Correct	327 ms	9236 KB	Output is correct
14	Correct	349 ms	9240 KB	Output is correct

Subtask #4

15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	967 ms	9272 KB	Output is correct
2	Correct	1148 ms	9304 KB	Output is correct
3	Correct	789 ms	9320 KB	Output is correct
4	Correct	698 ms	9284 KB	Output is correct
5	Correct	252 ms	9224 KB	Output is correct
6	Correct	628 ms	9292 KB	Output is correct
7	Correct	255 ms	9192 KB	Output is correct
8	Correct	407 ms	9296 KB	Output is correct
9	Correct	693 ms	9344 KB	Output is correct
10	Correct	704 ms	9264 KB	Output is correct
11	Correct	37 ms	3080 KB	Output is correct
12	Correct	422 ms	8508 KB	Output is correct
13	Correct	327 ms	9236 KB	Output is correct
14	Correct	349 ms	9240 KB	Output is correct
15	Correct	797 ms	9268 KB	Output is correct
16	Correct	642 ms	9308 KB	Output is correct
17	Correct	914 ms	9252 KB	Output is correct
18	Correct	733 ms	9344 KB	Output is correct
19	Correct	752 ms	9332 KB	Output is correct
20	Correct	722 ms	9332 KB	Output is correct
21	Correct	762 ms	9472 KB	Output is correct

Subtask #5

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 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	2 ms	640 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	28 ms	2276 KB	Output is correct
14	Correct	17 ms	2296 KB	Output is correct
15	Correct	17 ms	2268 KB	Output is correct
16	Correct	31 ms	2428 KB	Output is correct
17	Correct	23 ms	2220 KB	Output is correct
18	Correct	23 ms	2296 KB	Output is correct
19	Correct	967 ms	9272 KB	Output is correct
20	Correct	1148 ms	9304 KB	Output is correct
21	Correct	789 ms	9320 KB	Output is correct
22	Correct	698 ms	9284 KB	Output is correct
23	Correct	252 ms	9224 KB	Output is correct
24	Correct	628 ms	9292 KB	Output is correct
25	Correct	255 ms	9192 KB	Output is correct
26	Correct	407 ms	9296 KB	Output is correct
27	Correct	693 ms	9344 KB	Output is correct
28	Correct	704 ms	9264 KB	Output is correct
29	Correct	37 ms	3080 KB	Output is correct
30	Correct	422 ms	8508 KB	Output is correct
31	Correct	327 ms	9236 KB	Output is correct
32	Correct	349 ms	9240 KB	Output is correct
33	Correct	797 ms	9268 KB	Output is correct
34	Correct	642 ms	9308 KB	Output is correct
35	Correct	914 ms	9252 KB	Output is correct
36	Correct	733 ms	9344 KB	Output is correct
37	Correct	752 ms	9332 KB	Output is correct
38	Correct	722 ms	9332 KB	Output is correct
39	Correct	762 ms	9472 KB	Output is correct
40	Correct	1190 ms	10164 KB	Output is correct
41	Correct	42 ms	9308 KB	Output is correct
42	Correct	787 ms	10020 KB	Output is correct
43	Correct	735 ms	9824 KB	Output is correct
44	Correct	710 ms	9816 KB	Output is correct
45	Correct	1296 ms	12980 KB	Output is correct
46	Correct	54 ms	9464 KB	Output is correct
47	Correct	881 ms	13104 KB	Output is correct
48	Correct	784 ms	11372 KB	Output is correct
49	Correct	786 ms	12068 KB	Output is correct