Submission #670585

#	Time	Username	Problem	Language	Result	Execution time	Memory
670585		rainboy	Constellation 3 (JOI20_constellation3)	C11	100 / 100	282 ms	58764 KiB

constellation3

#include <stdio.h>
#include <stdlib.h>

#define N	200000
#define M	200000

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

int *ej[N], eo[N], *eh1[N], eo1[N], *eh2[N], eo2[N], aa[N], n;
int jj[M], yy[M], cc[M], m;

void append(int **ej, int *eo, int i, int j) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
	ej[i][o] = j;
}

int ta[N], tb[N], qu[N], cnt;

void dfs1(int i) {
	static int time;
	int o;

	qu[cnt++] = i, ta[i] = time++;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		dfs1(j);
	}
	for (o = eo1[i]; o--; ) {
		int h = eh1[i][o], lower, upper;

		lower = -1, upper = cnt - 1;
		while (upper - lower > 1) {
			int g = (lower + upper) / 2;

			if (aa[qu[g]] < yy[h])
				upper = g;
			else
				lower = g;
		}
		append(eh2, eo2, qu[upper], h);
	}
	tb[i] = time, cnt--;
}

long long ft[N];

void update(int i, int n, long long x) {
	while (i < n) {
		ft[i] += x;
		i |= i + 1;
	}
}

long long query(int i) {
	long long x = 0;

	while (i >= 0) {
		x += ft[i];
		i &= i + 1, i--;
	}
	return x;
}

long long dp[N];

void dfs2(int p, int i) {
	int o;
	long long x, y;

	x = 0;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		dfs2(i, j);
		x += dp[j];
	}
	y = 0;
	for (o = eo2[i]; o--; ) {
		int h = eh2[i][o];

		y = max(y, cc[h] - query(ta[jj[h]]) + (p == -1 ? 0 : query(ta[p])));
	}
	dp[i] = x + y;
	update(ta[i], n, y), update(tb[i], n, -y);
}

int main() {
	static int pp[N], qq[N];
	int h, i, j, r;
	long long sum;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]);
	cnt = 0;
	for (i = 0; i < n; i++) {
		while (cnt && aa[qu[cnt - 1]] <= aa[i])
			cnt--;
		pp[i] = cnt ? qu[cnt - 1] : -1;
		qu[cnt++] = i;
	}
	cnt = 0;
	for (i = n - 1; i >= 0; i--) {
		while (cnt && aa[qu[cnt - 1]] < aa[i])
			cnt--;
		qq[i] = cnt ? qu[cnt - 1] : -1;
		qu[cnt++] = i;
	}
	for (i = 0; i < n; i++) {
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
		eh1[i] = (int *) malloc(2 * sizeof *eh1[i]);
		eh2[i] = (int *) malloc(2 * sizeof *eh2[i]);
	}
	r = -1;
	for (i = 0; i < n; i++)
		if (pp[i] == -1 && qq[i] == -1)
			r = i;
		else if (qq[i] == -1 || pp[i] != -1 && aa[pp[i]] <= aa[qq[i]])
			append(ej, eo, pp[i], i);
		else
			append(ej, eo, qq[i], i);
	scanf("%d", &m);
	sum = 0;
	for (h = 0; h < m; h++) {
		scanf("%d%d%d", &j, &yy[h], &cc[h]), j--;
		jj[h] = j;
		append(eh1, eo1, j, h);
		sum += cc[h];
	}
	cnt = 0;
	dfs1(r);
	dfs2(-1, r);
	printf("%lld\n", sum - dp[r]);
	return 0;
}

Compilation message (stderr)

constellation3.c: In function 'append':
constellation3.c:15:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   15 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
constellation3.c: In function 'main':
constellation3.c:122:39: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  122 |   else if (qq[i] == -1 || pp[i] != -1 && aa[pp[i]] <= aa[qq[i]])
      |                           ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
constellation3.c:96:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
constellation3.c:98:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
constellation3.c:126:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |  scanf("%d", &m);
      |  ^~~~~~~~~~~~~~~
constellation3.c:129:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |   scanf("%d%d%d", &j, &yy[h], &cc[h]), j--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 65 / 65