Submission #482456

#	Time	Username	Problem	Language	Result	Execution time	Memory
482456		rainboy	3D Histogram (COCI20_histogram)	C11	110 / 110	638 ms	10088 KiB

histogram

#include <stdio.h>

#define N	200000
#define INF	0x3f3f3f3f

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; }

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

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

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

long long ans;

void solve_batch(int *aa, int *bb, int *ll, int *rr, int *jj, int m) {
	static int qu[N];
	int h, i, j, l_, r_, cnt;

	l_ = ll[jj[m - 1]], r_ = rr[jj[0]];
	cnt = 0;
	for (j = 0, i = l_, h = -1; j < m; j++) {
		int j_ = jj[j];

		while (i < rr[j_]) {
			xx[i] = aa[i], yy[i] = (long long) (-i + 1) * aa[i];
			if (cnt && xx[qu[cnt - 1]] == xx[i]) {
				if (yy[qu[cnt - 1]] < yy[i]) {
					cnt--;
					while (cnt >= 2 && cross(qu[cnt - 2], qu[cnt - 1], i) >= 0)
						cnt--;
					qu[cnt++] = i;
				}
			} else {
				while (cnt >= 2 && cross(qu[cnt - 2], qu[cnt - 1], i) >= 0)
					cnt--;
				qu[cnt++] = i;
			}
			i++;
		}
		for (h = 0; h < cnt; h++)
			ans = max(ans, eval(qu[h], j_) * bb[j_]);
	}
	cnt = 0;
	for (j = m - 1, i = r_ - 1, h = -1; j >= 0; j--) {
		int j_ = jj[j];

		while (i >= ll[j_]) {
			xx[i] = aa[i], yy[i] = (long long) (-i + 1) * aa[i];
			if (cnt && xx[qu[cnt - 1]] == xx[i]) {
				if (yy[qu[cnt - 1]] < yy[i]) {
					cnt--;
					while (cnt >= 2 && cross(qu[cnt - 2], qu[cnt - 1], i) <= 0)
						cnt--;
					qu[cnt++] = i;
				}
			} else {
				while (cnt >= 2 && cross(qu[cnt - 2], qu[cnt - 1], i) <= 0)
					cnt--;
				qu[cnt++] = i;
			}
			i--;
		}
		for (h = 0; h < cnt; h++)
			ans = max(ans, eval(qu[h], j_) * bb[j_]);
	}
}

void solve(int *aa, int *bb, int l, int r) {
	static int qqa[N], qqb[N], ppa[N], ppb[N], iia[N], iib[N], jj[N];
	int m = (l + r) / 2, i, j, cnt;

	if (r - l == 1) {
		ans = max(ans, (long long) aa[l] * bb[l]);
		return;
	}
	solve(aa, bb, l, m), solve(aa, bb, m, r);
	for (i = m - 1; i >= l; i--)
		qqa[i] = min(i + 1 == m ? INF : qqa[i + 1], aa[i]);
	for (i = m - 1; i >= l; i--)
		qqb[i] = min(i + 1 == m ? INF : qqb[i + 1], bb[i]);
	for (j = m; j < r; j++)
		ppa[j] = min(j == m ? INF : ppa[j - 1], aa[j]);
	for (j = m; j < r; j++)
		ppb[j] = min(j == m ? INF : ppb[j - 1], bb[j]);
	for (i = l, j = r - 1; i < m; i++) {
		while (j >= m && (qqa[i] > ppa[j] || qqb[i] > ppb[j]))
			j--;
		if (j >= m)
			ans = max(ans, (long long) qqa[i] * qqb[i] * (j - i + 1));
	}
	for (i = l, j = r - 1; j >= m; j--) {
		while (i < m && ppa[j] > qqa[i])
			i++;
		iia[j] = i;
	}
	for (i = l, j = r - 1; j >= m; j--) {
		while (i < m && ppb[j] > qqb[i])
			i++;
		iib[j] = i;
	}
	for (j = r - 1; j >= m; j--) {
		i = max(iia[j], iib[j]);
		if (i < m)
			ans = max(ans, (long long) ppa[j] * ppb[j] * (j - i + 1));
	}
	cnt = 0;
	for (j = r - 1; j >= m; j--)
		if (iia[j] < iib[j]) {
			if (cnt > 0 && iib[jj[cnt - 1]] < iia[j])
				solve_batch(qqb, ppa, iia, iib, jj, cnt), cnt = 0;
			jj[cnt++] = j;
		}
	if (cnt > 0)
		solve_batch(qqb, ppa, iia, iib, jj, cnt), cnt = 0;
	cnt = 0;
	for (j = r - 1; j >= m; j--)
		if (iib[j] < iia[j]) {
			if (cnt > 0 && iia[jj[cnt - 1]] < iib[j])
				solve_batch(qqa, ppb, iib, iia, jj, cnt), cnt = 0;
			jj[cnt++] = j;
		}
	if (cnt > 0)
		solve_batch(qqa, ppb, iib, iia, jj, cnt), cnt = 0;
}

int main() {
	static int aa[N], bb[N];
	int n, i;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d%d", &aa[i], &bb[i]);
	ans = 0;
	solve(aa, bb, 0, n);
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

histogram.c: In function 'main':
histogram.c:136:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
histogram.c:138:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |   scanf("%d%d", &aa[i], &bb[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 90 / 90