oj.uz

답안 #1050822

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1050822 2024-08-09T14:53:57 Z rainboy Tricks of the Trade (CEOI23_trade) C
10 / 100
 8000 ms 24336 KB 
#include <stdio.h>
#include <string.h>

#define N	250000
#define LN	18	/* LN = ceil(log2(N)) */
#define N_	(N * (LN + 1) + 1)
#define INF	0x3f3f3f3f3f3f3f3fLL

int min(int a, int b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }

unsigned int Z = 12345;

int rand_() {
	return (Z *= 3) >> 1;
}

long long xx[N + 1]; int yy[N], yy_[N], n, m, k;

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (yy[ii[j]] == yy[i_])
				j++;
			else if (yy[ii[j]] < yy[i_]) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		sort(ii, l, i);
		l = k;
	}
}

int ll[N_], rr[N_], kk[N_]; long long ss[N_];

int update(int t, int l, int r, int i) {
	static int _ = 1;
	int t_ = _++;

	ll[t_] = ll[t], rr[t_] = rr[t], kk[t_] = kk[t] + 1, ss[t_] = ss[t] + yy_[i];
	if (r - l > 1) {
		int m = (l + r) / 2;

		if (i < m)
			ll[t_] = update(ll[t_], l, m, i);
		else
			rr[t_] = update(rr[t_], m, r, i);
	}
	return t_;
}

long long s_; int y_;

void query(int t1, int t2, int l, int r, int k) {
	int m;

	if (r - l == 1) {
		s_ += (long long) yy_[l] * k, y_ = l;
		return;
	}
	m = (l + r) / 2;
	if (k <= kk[rr[t2]] - kk[rr[t1]])
		query(rr[t1], rr[t2], m, r, k);
	else
		s_ += ss[rr[t2]] - ss[rr[t1]], query(ll[t1], ll[t2], l, m, k - (kk[rr[t2]] - kk[rr[t1]]));
}

int tt[N + 1];

long long f(int i, int j) {
	s_ = 0, y_ = -1, query(tt[i], tt[j], 0, m, k);
	return s_ - (xx[j] - xx[i]);
}

int find_j(int i1, int i2) {
	int lower = i2 + k - 1, upper = n + 1;

	while (upper - lower > 1) {
		int j = (lower + upper) / 2;

		if (f(i1, j) <= f(i2, j))
			upper = j;
		else
			lower = j;
	}
	return upper;
}

int find_i(int j1, int j2) {
	int lower = -1, upper = j1 - k + 1;

	while (upper - lower > 1) {
		int i = (lower + upper) / 2;

		if (f(i, j1) >= f(i, j2))
			lower = i;
		else
			upper = i;
	}
	return lower;
}

int st[N_ * 2], n_;

void build() {
	n_ = 1;
	while (n_ < n)
		n_ <<= 1;
	memset(st, 0x3f, n_ * 2 * sizeof *st);
}

void update_(int l, int r, int y) {
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			st[l] = min(st[l], y), l++;
		if ((r & 1) == 0)
			st[r] = min(st[r], y), r--;
	}
}

int main() {
	static int ii[N + 1], jj[N + 1], qu[N + 1], ii_[N + 1], jj_[N + 1];
	static long long xxj[N + 1], xxi[N + 1];
	static char cc[N + 1];
	int head, cnt, i, j, y;
	long long x_;

	scanf("%d%d", &n, &k);
	for (i = 1; i <= n; i++)
		scanf("%lld", &xx[i]), xx[i] += xx[i - 1];
	for (i = 0; i < n; i++)
		scanf("%d", &yy[i]);
	for (i = 0; i < n; i++)
		ii[i] = i;
	sort(ii, 0, n);
	for (i = 0, m = 0; i < n; i = j) {
		j = i, y = yy[ii[i]];
		while (j < n && yy[ii[j]] == y)
			yy[ii[j++]] = m;
		yy_[m++] = y;
	}
	for (i = 0; i < n; i++)
		tt[i + 1] = update(tt[i], 0, m, yy[i]);
	for (i = 0; i < n; i++)
		for (j = i + k; j <= n; j++)
			query(tt[i], tt[j], 0, m, k);
	x_ = -INF;
	head = 0, cnt = 0;
	for (j = k; j <= n; j++) {
		while (cnt >= 2 && jj[head] <= j)
			head++, cnt--;
		i = j - k;
		while (cnt >= 2 && f(i, jj[head + cnt - 2]) >= f(qu[head + cnt - 1], jj[head + cnt - 2]))
			cnt--;
		if (cnt)
			jj[head + cnt - 1] = find_j(qu[head + cnt - 1], i);
		qu[head + cnt++] = i;
		while (cnt >= 2 && jj[head] <= j)
			head++, cnt--;
		i = qu[head];
		ii_[j] = i, xxj[j] = f(i, j);
		x_ = max(x_, xxj[j]);
	}
	head = 0, cnt = 0;
	for (i = n - k; i >= 0; i--) {
		while (cnt >= 2 && ii[head] >= i)
			head++, cnt--;
		j = i + k;
		while (cnt >= 2 && f(ii[head + cnt - 2], j) >= f(ii[head + cnt - 2], qu[head + cnt - 1]))
			cnt--;
		if (cnt)
			ii[head + cnt - 1] = find_i(j, qu[head + cnt - 1]);
		qu[head + cnt++] = j;
		while (cnt >= 2 && ii[head] >= i)
			head++, cnt--;
		j = qu[head];
		jj_[i] = j, xxi[i] = f(i, j);
		x_ = max(x_, xxi[i]);
	}
	build();
	for (j = k; j <= n; j++)
		if (xxj[j] == x_) {
			i = ii_[j];
			s_ = 0, y_ = -1, query(tt[i], tt[j], 0, m, k);
			update_(i, j - 1, y_);
		}
	for (i = 0; i <= n - k; i++)
		if (xxi[i] == x_) {
			j = jj_[i];
			s_ = 0, y_ = -1, query(tt[i], tt[j], 0, m, k);
			update_(i, j - 1, y_);
		}
	for (i = 1; i < n_; i++)
		st[i << 1 | 0] = min(st[i << 1 | 0], st[i]), st[i << 1 | 1] = min(st[i << 1 | 1], st[i]);
	for (i = 0; i < n; i++)
		cc[i] = st[n_ + i] <= yy[i] ? '1' : '0';
	printf("%lld\n", x_);
	printf("%s\n", cc);
	return 0;
}

Compilation message

trade.c: In function 'main':
trade.c:133:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |  scanf("%d%d", &n, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~
trade.c:135:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |   scanf("%lld", &xx[i]), xx[i] += xx[i - 1];
      |   ^~~~~~~~~~~~~~~~~~~~~
trade.c:137:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |   scanf("%d", &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 12632 KB Output is correct
2 Correct 1 ms 12636 KB Output is correct

Subtask #1
5.0 / 10.0

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

Subtask #2
5.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 12636 KB Output is correct
2 Correct 1 ms 12636 KB Output is correct
3 Correct 1 ms 12636 KB Output is correct
4 Correct 1 ms 12636 KB Output is correct
5 Correct 1 ms 12804 KB Output is correct
6 Partially correct 1 ms 12636 KB Partially correct
7 Correct 1 ms 12636 KB Output is correct
8 Correct 1 ms 12636 KB Output is correct
9 Correct 1 ms 12636 KB Output is correct
10 Correct 2 ms 12636 KB Output is correct
11 Partially correct 1 ms 12636 KB Partially correct
12 Correct 1 ms 12636 KB Output is correct
13 Correct 1 ms 12636 KB Output is correct
14 Correct 1 ms 12636 KB Output is correct
15 Correct 1 ms 12636 KB Output is correct
16 Correct 1 ms 12636 KB Output is correct
17 Partially correct 2 ms 12636 KB Partially correct
18 Correct 2 ms 12636 KB Output is correct
19 Correct 1 ms 12636 KB Output is correct
20 Correct 1 ms 12636 KB Output is correct
21 Correct 1 ms 12636 KB Output is correct
22 Partially correct 1 ms 12724 KB Partially correct
23 Correct 2 ms 13660 KB Output is correct
24 Correct 440 ms 14456 KB Output is correct
25 Correct 508 ms 14408 KB Output is correct
26 Correct 604 ms 14416 KB Output is correct
27 Correct 33 ms 13132 KB Output is correct
28 Correct 237 ms 13648 KB Output is correct
29 Correct 103 ms 14224 KB Output is correct

Subtask #3
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 12632 KB Output is correct
2 Execution timed out 8093 ms 24336 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 12632 KB Output is correct
2 Execution timed out 8093 ms 24336 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 12632 KB Output is correct
2 Correct 1 ms 12636 KB Output is correct
3 Correct 1 ms 12636 KB Output is correct
4 Correct 1 ms 12636 KB Output is correct
5 Correct 1 ms 12636 KB Output is correct
6 Correct 1 ms 12636 KB Output is correct
7 Correct 1 ms 12804 KB Output is correct
8 Partially correct 1 ms 12636 KB Partially correct
9 Correct 1 ms 12636 KB Output is correct
10 Correct 1 ms 12636 KB Output is correct
11 Correct 1 ms 12636 KB Output is correct
12 Correct 2 ms 12636 KB Output is correct
13 Partially correct 1 ms 12636 KB Partially correct
14 Correct 1 ms 12636 KB Output is correct
15 Correct 1 ms 12636 KB Output is correct
16 Correct 1 ms 12636 KB Output is correct
17 Correct 1 ms 12636 KB Output is correct
18 Correct 1 ms 12636 KB Output is correct
19 Partially correct 2 ms 12636 KB Partially correct
20 Correct 2 ms 12636 KB Output is correct
21 Correct 1 ms 12636 KB Output is correct
22 Correct 1 ms 12636 KB Output is correct
23 Correct 1 ms 12636 KB Output is correct
24 Partially correct 1 ms 12724 KB Partially correct
25 Correct 2 ms 13660 KB Output is correct
26 Correct 440 ms 14456 KB Output is correct
27 Correct 508 ms 14408 KB Output is correct
28 Correct 604 ms 14416 KB Output is correct
29 Correct 33 ms 13132 KB Output is correct
30 Correct 237 ms 13648 KB Output is correct
31 Correct 103 ms 14224 KB Output is correct
32 Correct 1 ms 12632 KB Output is correct
33 Execution timed out 8093 ms 24336 KB Time limit exceeded
34 Halted 0 ms 0 KB -