oj.uz

답안 #482456

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
482456 2021-10-24T15:30:35 Z rainboy 3D Histogram (COCI20_histogram) C
110 / 110
 638 ms 10088 KB 
#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

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.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 3 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct

Subtask #2
90.0 / 90.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 3 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 117 ms 9988 KB Output is correct
14 Correct 93 ms 9832 KB Output is correct
15 Correct 96 ms 9552 KB Output is correct
16 Correct 162 ms 10088 KB Output is correct
17 Correct 534 ms 10028 KB Output is correct
18 Correct 638 ms 9884 KB Output is correct
19 Correct 537 ms 9888 KB Output is correct
20 Correct 515 ms 9848 KB Output is correct
21 Correct 194 ms 9944 KB Output is correct
22 Correct 514 ms 9972 KB Output is correct
23 Correct 10 ms 1228 KB Output is correct
24 Correct 122 ms 9628 KB Output is correct