oj.uz

Submission #1050819

# Submission time Handle Problem Language Result Execution time Memory
1050819 2024-08-09T14:51:25 Z rainboy Tricks of the Trade (CEOI23_trade) C
10 / 100
 8000 ms 16096 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, 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, 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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 12636 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #1
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 12636 KB Output is correct
3 Partially correct 1 ms 12636 KB Partially correct
4 Partially correct 1 ms 348 KB Partially correct
5 Correct 0 ms 348 KB Output is correct
6 Partially correct 2 ms 12824 KB Partially correct
7 Partially correct 2 ms 12636 KB Partially correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Partially correct 1 ms 348 KB Partially correct
11 Partially correct 0 ms 348 KB Partially correct

Subtask #2
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 12636 KB Output is correct
3 Partially correct 1 ms 12636 KB Partially correct
4 Partially correct 1 ms 348 KB Partially correct
5 Correct 0 ms 348 KB Output is correct
6 Partially correct 2 ms 12824 KB Partially correct
7 Partially correct 2 ms 12636 KB Partially correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Partially correct 1 ms 348 KB Partially correct
11 Partially correct 0 ms 348 KB Partially correct
12 Correct 1 ms 12636 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Partially correct 1 ms 12636 KB Partially correct
15 Partially correct 2 ms 12892 KB Partially correct
16 Correct 1 ms 432 KB Output is correct
17 Partially correct 2 ms 348 KB Partially correct
18 Partially correct 1 ms 348 KB Partially correct
19 Correct 1 ms 12636 KB Output is correct
20 Correct 2 ms 12632 KB Output is correct
21 Partially correct 1 ms 348 KB Partially correct
22 Partially correct 2 ms 12636 KB Partially correct
23 Correct 2 ms 13660 KB Output is correct
24 Partially correct 453 ms 2524 KB Partially correct
25 Partially correct 525 ms 6224 KB Partially correct
26 Partially correct 659 ms 14416 KB Partially correct
27 Correct 37 ms 920 KB Output is correct
28 Correct 248 ms 13736 KB Output is correct
29 Correct 107 ms 10064 KB Output is correct

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 12636 KB Output is correct
2 Execution timed out 8092 ms 16096 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 12636 KB Output is correct
2 Execution timed out 8092 ms 16096 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 12636 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 12636 KB Output is correct
5 Partially correct 1 ms 12636 KB Partially correct
6 Partially correct 1 ms 348 KB Partially correct
7 Correct 0 ms 348 KB Output is correct
8 Partially correct 2 ms 12824 KB Partially correct
9 Partially correct 2 ms 12636 KB Partially correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Partially correct 1 ms 348 KB Partially correct
13 Partially correct 0 ms 348 KB Partially correct
14 Correct 1 ms 12636 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Partially correct 1 ms 12636 KB Partially correct
17 Partially correct 2 ms 12892 KB Partially correct
18 Correct 1 ms 432 KB Output is correct
19 Partially correct 2 ms 348 KB Partially correct
20 Partially correct 1 ms 348 KB Partially correct
21 Correct 1 ms 12636 KB Output is correct
22 Correct 2 ms 12632 KB Output is correct
23 Partially correct 1 ms 348 KB Partially correct
24 Partially correct 2 ms 12636 KB Partially correct
25 Correct 2 ms 13660 KB Output is correct
26 Partially correct 453 ms 2524 KB Partially correct
27 Partially correct 525 ms 6224 KB Partially correct
28 Partially correct 659 ms 14416 KB Partially correct
29 Correct 37 ms 920 KB Output is correct
30 Correct 248 ms 13736 KB Output is correct
31 Correct 107 ms 10064 KB Output is correct
32 Correct 1 ms 12636 KB Output is correct
33 Execution timed out 8092 ms 16096 KB Time limit exceeded
34 Halted 0 ms 0 KB -