oj.uz

답안 #441885

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
441885 2021-07-06T13:35:54 Z rainboy Pyramid Base (IOI08_pyramid_base) C
80 / 100
 5000 ms 49352 KB 
/* discussed with Dukkha on performance optimization */
#if 1
#pragma GCC optimize("O3")
#endif
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define M	1000000
#define P	400000

int xmin[P], xmax[P], ymin[P], ymax[P], imin[P], imax[P], m, n, p, a;
short cc[P];
unsigned int b;

int iay[P * 2][3];

int compare_ymin(const void *a, const void *b) {
	int i = *(int *) a;
	int j = *(int *) b;

	return ymin[i] - ymin[j];
}

int compare_ymax(const void *a, const void *b) {
	int i = *(int *) a;
	int j = *(int *) b;

	return ymax[i] - ymax[j];
}

#define K	(1 << 20)

unsigned int tt[K + K][2];

void push(int i) {
	int j = 1, b;

	for (b = K >> 1; b; b >>= 1) {
		unsigned int x;

		if ((x = tt[j][1])) {
			int j0 = j * 2 + 0;
			int j1 = j * 2 + 1;

			tt[j0][0] += x, tt[j0][1] += x;
			tt[j1][0] += x, tt[j1][1] += x;
			tt[j][1] = 0;
		}
		j <<= 1;
		if (i & b)
			j ^= 1;
	}
}

void update(int i, int c) {	/* assumes i < K */
	if (i <= 0)
		return;
	push(i);
	i += K;
	while (i > 1) {
		int t0, t1;

		if (i & 1)
			tt[i ^ 1][0] += c, tt[i ^ 1][1] += c;
		t0 = tt[i][0];
		t1 = tt[i ^ 1][0];
		tt[i >>= 1][0] = t0 < t1 ? t0 : t1;
	}
}

unsigned int query(int i) {
	unsigned int min = -1, t;

	push(i);
	i += K;
	while (i > 1) {
		if (i & 1 && min > (t = tt[i ^ 1][0]))
			min = t;
		i >>= 1;
	}
	return min;
}

void merge() {
	int h, i, j;

	for (i = j = 0; (h = i + j) < p + p; ) {
		int *zz = iay[h];

		if (j == p) {
			zz[1] = 1;
			zz[2] = ymin[zz[0] = imin[i++]] - a + 1;
		} else if (i == p) {
			zz[1] = 0;
			zz[2] = ymax[zz[0] = imax[j++]] + 1;
		} else {
			int y1 = ymin[imin[i]] - a + 1;
			int y0 = ymax[imax[j]] + 1;

			if (y1 < y0) {
				zz[0] = imin[i++];
				zz[1] = 1;
				zz[2] = y1;
			} else {
				zz[0] = imax[j++];
				zz[1] = 0;
				zz[2] = y0;
			}
		}
	}
}

int check() {
	int h, j, zero;

	memset(tt, 0, sizeof tt);
	if (b == 0) {
		tt[1][0] = tt[1][1] = 1;
		update(m - a + 1, -1);
	}
	merge();
	zero = 0;
	for (h = 0; h < p * 2; h = j) {
		int y = iay[h][2];

		if (y + a - 1 >= n)	/* top boundary */
			break;
		if (!zero && y > 0) {
			zero = 1;
			if ((b ? query(m - a + 1) : tt[1][0]) <= b)
				return 1;
		}
		for (j = h; j < p * 2 && iay[j][2] == y; j++) {
			int i_ = iay[j][0];
			int c = iay[j][1] ? cc[i_] : -cc[i_];

			update(xmax[i_] + 1, c);
			update(xmin[i_] - a + 1, -c);
		}
		if (y < 0)	/* bottom boundary */
			continue;
		if ((b ? query(m - a + 1) : tt[1][0]) <= b)
			return 1;
	}
	return 0;
}

#define getchar getchar_unlocked
int getint() {
	int c, n;

	while ((c = getchar()) < '0')
		;
	n = c - '0';
	while ((c = getchar()) >= '0')
		n = n * 10 + (c - '0');
	return n;
}

int main() {
	int i, lower, upper;

#if 0
	scanf("%d%d%d%d", &m, &n, &b, &p);
#else
	m = getint();
	n = getint();
	b = getint();
	p = getint();
#endif
	for (i = 0; i < p; i++) {
		int x1, y1, x2, y2, c;

#if 0
		scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
#else
		x1 = getint();
		y1 = getint();
		x2 = getint();
		y2 = getint();
		c = getint();
#endif
		xmin[i] = x1 - 1;
		xmax[i] = x2 - 1;
		ymin[i] = y1 - 1;
		ymax[i] = y2 - 1;
		cc[i] = c;
		imin[i] = imax[i] = i;
	}
	qsort(imin, p, sizeof *imin, compare_ymin);
	qsort(imax, p, sizeof *imax, compare_ymax);
	a = 1;
	if (check()) {
		int cnt = 0, low = 1;

		lower = 1, upper = (m < n ? m : n) + 1;
		while (upper - lower > 1) {
			a = (lower + upper) / 2;
			cnt++;
			if (check()) {
				lower = a;
				low = 1;
			} else {
				upper = a;
				low = 0;
			}
		}
	} else
		lower = 0;
	printf("%d\n", lower);
	return 0;
}

Compilation message

pyramid_base.c: In function 'main':
pyramid_base.c:196:16: warning: variable 'low' set but not used [-Wunused-but-set-variable]
  196 |   int cnt = 0, low = 1;
      |                ^~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 16716 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 16844 KB Output is correct

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 16676 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 16720 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 16716 KB Output is correct

Subtask #6
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 16716 KB Output is correct
2 Correct 10 ms 16716 KB Output is correct

Subtask #7
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 70 ms 16744 KB Output is correct
2 Correct 61 ms 16716 KB Output is correct

Subtask #8
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 17104 KB Output is correct
2 Correct 61 ms 17116 KB Output is correct
3 Correct 74 ms 17100 KB Output is correct

Subtask #9
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 172 ms 17896 KB Output is correct
2 Correct 249 ms 17844 KB Output is correct
3 Correct 246 ms 17904 KB Output is correct

Subtask #10
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 251 ms 18380 KB Output is correct
2 Correct 121 ms 18224 KB Output is correct
3 Correct 56 ms 18124 KB Output is correct
4 Correct 520 ms 18500 KB Output is correct

Subtask #11
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 450 ms 18884 KB Output is correct
2 Correct 642 ms 18852 KB Output is correct
3 Correct 281 ms 18844 KB Output is correct

Subtask #12
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 415 ms 19184 KB Output is correct
2 Correct 814 ms 19300 KB Output is correct
3 Correct 768 ms 19176 KB Output is correct
4 Correct 830 ms 19184 KB Output is correct
5 Correct 788 ms 19216 KB Output is correct
6 Correct 300 ms 19276 KB Output is correct

Subtask #13
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4416 ms 33080 KB Output is correct
2 Correct 1426 ms 32364 KB Output is correct

Subtask #14
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5024 ms 41304 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5048 ms 49352 KB Time limit exceeded
2 Halted 0 ms 0 KB -