Submission #545907

#	Time	Username	Problem	Language	Result	Execution time	Memory
545907		rainboy	Building Bridges (CEOI17_building)	C11	100 / 100	94 ms	8656 KiB

building

#include <stdio.h>

#define N	100000
#define INF	0x3f3f3f3f3f3f3f3fLL

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

unsigned int X = 12345;

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

long long xx[N], yy[N];

long long cross2(long long x1, long long y1, long long x2, long long y2) {
	return x1 * y2 - x2 * y1;
}

long long cross(int i, int j, int k) {
	return cross2(xx[j] - xx[i], yy[j] - yy[i], xx[k] - xx[i], yy[k] - yy[i]);
}

int zz[1 + N * 2], ll[1 + N * 2], rr[1 + N * 2], ii[1 + N * 2], jj[1 + N * 2], u_, l_, r_;

int node(int i, int j) {
	static int _ = 1;

	zz[_] = rand_();
	ii[_] = i, jj[_] = j;
	return _++;
}

void split_x(int u, int i) {
	if (u == 0) {
		l_ = r_ = 0;
		return;
	}
	if (xx[ii[u]] < xx[i] || xx[ii[u]] == xx[i] && yy[ii[u]] <= yy[i]) {
		split_x(rr[u], i);
		rr[u] = l_, l_ = u;
	} else {
		split_x(ll[u], i);
		ll[u] = r_, r_ = u;
	}
}

int mode;

int compare(int i, int j, int k) {
	return (mode == 0) == (cross(i, j, k) > 0) ? -1 : 1;
}

void split_c(int u, int i) {
	if (u == 0) {
		l_ = r_ = 0;
		return;
	}
	if (compare(ii[u], jj[u], i) < 0) {
		split_c(rr[u], i);
		rr[u] = l_, l_ = u;
	} else {
		split_c(ll[u], i);
		ll[u] = r_, r_ = u;
	}
}

int merge(int u, int v) {
	if (u == 0)
		return v;
	if (v == 0)
		return u;
	if (zz[u] < zz[v]) {
		rr[u] = merge(rr[u], v);
		return u;
	} else {
		ll[v] = merge(u, ll[v]);
		return v;
	}
}

int first(int u) { return ll[u] == 0 ? u : first(ll[u]); }
int last(int u) { return rr[u] == 0 ? u : last(rr[u]); }

int il, ir;

void update(int i) {
	if (il == -1)
		il = ir = i;
	else if (xx[il] > xx[i] || xx[il] == xx[i] && yy[il] > yy[i]) {
		mode = 1, split_c(u_, i), u_ = merge(node(i, r_ ? ii[first(r_)] : ir), r_);
		il = i;
	} else if (xx[ir] < xx[i] || xx[ir] == xx[i] && yy[ir] < yy[i]) {
		mode = 0, split_c(u_, i), u_ = merge(l_, node(l_ ? jj[last(l_)] : il, i));
		ir = i;
	} else {
		int u, l, r;

		if (il == ir)
			return;
		split_x(u_, i);
		l = l_, r = r_, u = last(l);
		if (cross(ii[u], jj[u], i) < 0) {
			mode = 0, split_c(l, i), l = merge(l_, node(l_ ? jj[last(l_)] : il, i));
			mode = 1, split_c(r, i), r = merge(node(i, r_ ? ii[first(r_)] : ir), r_);
		}
		u_ = merge(l, r);
	}
}

long long eval(int i, int x, int y) {
	return xx[i] * x + yy[i] * y;
}

long long query(int x, int y) {
	int u;
	long long z;

	if (il == ir)
		return eval(il, x, y);
	u = u_, z = -INF;
	while (u) {
		long long zi = eval(ii[u], x, y), zj = eval(jj[u], x, y);
		
		z = max(z, max(zi, zj));
		u = zi > zj ? ll[u] : rr[u];
	}
	return z;
}

int main() {
	static int hh[N];
	static long long ww[N], dp[N];
	int n, i;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d", &hh[i]);
	for (i = 0; i < n; i++)
		scanf("%lld", &ww[i]);
	for (i = 1; i < n; i++)
		ww[i] += ww[i - 1];
	il = ir = -1;
	dp[0] = 0;
	xx[0] = hh[0] * 2, yy[0] = dp[0] + (long long) hh[0] * hh[0] - ww[0], update(0);
	for (i = 1; i < n; i++) {
		dp[i] = -query(hh[i], -1) + (long long) hh[i] * hh[i] + ww[i - 1];
		xx[i] = hh[i] * 2, yy[i] = dp[i] + (long long) hh[i] * hh[i] - ww[i], update(i);
	}
	printf("%lld\n", dp[n - 1]);
	return 0;
}

Compilation message (stderr)

building.c: In function 'split_x':
building.c:39:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   39 |  if (xx[ii[u]] < xx[i] || xx[ii[u]] == xx[i] && yy[ii[u]] <= yy[i]) {
      |                           ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
building.c: In function 'update':
building.c:90:45: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   90 |  else if (xx[il] > xx[i] || xx[il] == xx[i] && yy[il] > yy[i]) {
      |                             ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
building.c:93:47: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   93 |  } else if (xx[ir] < xx[i] || xx[ir] == xx[i] && yy[ir] < yy[i]) {
      |                               ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
building.c: In function 'main':
building.c:136:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
building.c:138:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |   scanf("%d", &hh[i]);
      |   ^~~~~~~~~~~~~~~~~~~
building.c:140:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |   scanf("%lld", &ww[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40