oj.uz

답안 #482473

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
482473 2021-10-24T16:25:04 Z rainboy 3D Histogram (COCI20_histogram) C
110 / 110
 135 ms 10048 KB 
#include <stdio.h>
#include <stdlib.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, cnt;

	cnt = 0;
	for (j = 0, i = rr[jj[0]], 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++;
		}
		if (cnt) {
			if (h < 0)
				h = 0;
			if (h >= cnt)
				h = cnt - 1;
			while (h + 1 < cnt && eval(qu[h], j_) < eval(qu[h + 1], j_))
				h++;
			while (h > 0 && eval(qu[h], j_) < eval(qu[h - 1], j_))
				h--;
			ans = max(ans, eval(qu[h], j_) * bb[j_]);
		}
	}
	cnt = 0;
	for (j = m - 1, i = rr[jj[0]] - 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--;
		}
		if (cnt) {
			if (h < 0)
				h = 0;
			if (h >= cnt)
				h = cnt - 1;
			while (h + 1 < cnt && eval(qu[h], j_) < eval(qu[h + 1], j_))
				h++;
			while (h > 0 && eval(qu[h], j_) < eval(qu[h - 1], j_))
				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 && iib[jj[0]] < iia[j])
				solve_batch(qqb, ppa, iia, iib, jj, cnt), cnt = 0;
			jj[cnt++] = j;
		}
	if (cnt)
		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 && iia[jj[0]] < iib[j])
				solve_batch(qqa, ppb, iib, iia, jj, cnt), cnt = 0;
			jj[cnt++] = j;
		}
	if (cnt)
		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:154:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
histogram.c:156:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |   scanf("%d%d", &aa[i], &bb[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 0 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 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 112 ms 9940 KB Output is correct
14 Correct 97 ms 9844 KB Output is correct
15 Correct 119 ms 9544 KB Output is correct
16 Correct 116 ms 9968 KB Output is correct
17 Correct 131 ms 10048 KB Output is correct
18 Correct 111 ms 9908 KB Output is correct
19 Correct 117 ms 9924 KB Output is correct
20 Correct 115 ms 9740 KB Output is correct
21 Correct 106 ms 9972 KB Output is correct
22 Correct 135 ms 9924 KB Output is correct
23 Correct 11 ms 1228 KB Output is correct
24 Correct 90 ms 9540 KB Output is correct