Submission #1050834

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050834		rainboy	Tricks of the Trade (CEOI23_trade)	C11	60 / 100	2069 ms	108372 KiB

trade

#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]);
	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();
	if (n <= 200) {
		for (i = 0; i < n; i++)
			for (j = i + k; j <= n; j++)
				if (f(i, j) == x_) {
					s_ = 0, y_ = -1, query(tt[i], tt[j], 0, m, k);
					update_(i, j - 1, y_);
				}
	} else {
		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 (stderr)

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
• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 5 / 10
• Subtask 4: 10 / 25
• Subtask 5: 25 / 45