Submission #788188

#	Time	Username	Problem	Language	Result	Execution time	Memory
788188		rainboy	Fruits (NOI22_fruits)	C11	100 / 100	217 ms	31416 KiB

Main

#include <stdio.h>
#include <string.h>

#define N	400000
#define INF	0x3f3f3f3f3f3f3f3fLL

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

int n, k;
int ww[N]; long long ss[N + 1];
int xx[N], yy[N], dd[N], pp[N], qq[N], hh[N], tt[N], ii[N]; long long dp[N];

int cross(int i, int j) {
	int lower = -1, upper = k - yy[j] + 1;

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

		if (dp[i] - ss[yy[i] + d] > dp[j] - ss[yy[j] + d])
			upper = d;
		else
			lower = d;
	}
	return lower;
}

void merge(int i, int j) {
	int u, v, d;

	u = tt[i], v = hh[j];
	while (1) {
		d = cross(u, v);
		if (u != hh[i] && cross(pp[u], u) <= d)
			u = pp[u];
		else if (v != tt[j] && cross(v, qq[v]) >= d)
			v = qq[v];
		else {
			qq[u] = v, pp[v] = u;
			break;
		}
	}
	hh[j] = hh[i];
}

long long query(int i, int d) {
	while (hh[i] != tt[i] && cross(hh[i], qq[hh[i]]) >= d)
		hh[i] = qq[hh[i]];
	return dp[hh[i]] - ss[yy[hh[i]] + d];
}

void dc(int il, int ir, int jl, int jr) {
	int i, i_, j, d;
	long long z, z_;

	if (jl > jr)
		return;
	j = (jl + jr) / 2;
	d = k - yy[j];
	z_ = -INF;
	for (i_ = i = max(il, ii[j] + 1); i <= ir && i <= j; i++)
		if (dp[i] != -INF) {
			z = dp[i] - ss[yy[i] + d];
			if (z_ < z)
				z_ = z, i_ = i;
		}
	if (i_ == il - 1)
		i_ = il;
	if (ii[j] >= 0)
		z_ = max(z_, dp[ii[j]] - ss[xx[ii[j]]]);
	else
		z_ = max(z_, -ss[d]);
	z_ += ss[k];
	dc(il, i_, jl, j - 1), printf("%lld ", z_), dc(i_, ir, j + 1, jr);
}

int main() {
	static int aa[N], qu[N];
	int cnt, h, i, i_, j, a, y;

	scanf("%d", &n);
	memset(ii, -1, n * sizeof *ii);
	for (i = 0; i < n; i++) {
		scanf("%d", &aa[i]), aa[i]--;
		if (aa[i] >= 0)
			ii[aa[i]] = i;
	}
	for (a = 0; a < n; a++)
		scanf("%d", &ww[a]);
	k = 0;
	for (a = 0; a < n; a++)
		if ((i = ii[a]) != -1)
			xx[i] = k;
		else
			ss[k + 1] = ss[k] + ww[a], k++;
	for (i = 0; i < n; i++)
		pp[i] = qq[i] = -1, hh[i] = tt[i] = i;
	y = 0, a = -1, cnt = 0, h = 0;
	for (j = 0; j < n; j++) {
		if (aa[j] < 0)
			y++;
		yy[j] = y, dd[j] = xx[j] - yy[j];
		a = max(a, aa[j]);
		if (aa[j] == a && dd[j] >= 0) {
			i_ = -1;
			while (cnt && dd[i = qu[cnt - 1]] < dd[j]) {
				if (i_ == -1)
					i_ = i;
				else
					merge(i, i_);
				cnt--;
			}
			dp[j] = cnt ? dp[i] - ss[xx[i]] : -ss[dd[j]];
			if (i_ != -1)
				dp[j] = max(dp[j], query(i_, dd[j]));
			dp[j] += ss[xx[j]] + ww[aa[j]];
			if (i_ != -1)
				merge(i_, j);
			qu[cnt++] = j;
		} else
			dp[j] = -INF;
		h = min(h, cnt);
		while (h < cnt && dd[qu[h]] >= k - y)
			h++;
		ii[j] = h == 0 ? -1 : qu[h - 1];
	}
	dc(0, n - 1, 0, n - 1), printf("\n");
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:81:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
Main.c:84:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |   scanf("%d", &aa[i]), aa[i]--;
      |   ^~~~~~~~~~~~~~~~~~~
Main.c:89:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |   scanf("%d", &ww[a]);
      |   ^~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 5 / 5
• Subtask 3: 11 / 11
• Subtask 4: 13 / 13
• Subtask 5: 23 / 23
• Subtask 6: 42 / 42