제출 #683149

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
683149		rainboy	Cultivation (JOI17_cultivation)	C11	5 / 100	2083 ms	352 KiB

cultivation

#include <stdio.h>

#define N	300
#define N_	(1 << 9)	/* N_ = pow2(ceil(log2(N))) */
#define N2	(N * 2)
#define INF	0x7fffffff
#define LINF	0x3f3f3f3f3f3f3f3fLL

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

unsigned int X = 12345;

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

int xx[N], yy[N], yy_[N], xx_[N2], xx1[N2], n, x_, y_;

int *zz;

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (zz[ii[j]] == zz[i_])
				j++;
			else if (zz[ii[j]] < zz[i_]) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		sort(ii, l, i);
		l = k;
	}
}

int stl[N_ * 2], str[N_ * 2], stc[N_ * 2], n_;

void pul(int i) {
	int l = i << 1, r = l | 1;

	stl[i] = min(stl[l], stl[r]);
	str[i] = max(str[l], str[r]);
	stc[i] = max(stc[l], stc[r]);
	if (str[l] != -1 && stl[r] != INF)
		stc[i] = max(stc[i], stl[r] - str[l] - 1);
}

int kk[N];

void update(int i, int x) {
	kk[i] += x;
	if (kk[i] == 0)
		stl[n_ + i] = INF, str[n_ + i] = -1, stc[n_ + i] = 0;
	else
		stl[n_ + i] = yy_[i], str[n_ + i] = yy_[i], stc[n_ + i] = 0;
	i += n_;
	while (i > 1)
		pul(i >>= 1);
}

long long solve(int w) {
	static int ii[N2], ll[N2], rr[N2], cc[N2];
	int m, h, i, x, l, r, c;
	long long ans;

	if (w < 0)
		return LINF;
	for (i = 0; i < n; i++)
		xx_[i << 1 | 0] = xx[i], xx_[i << 1 | 1] = xx[i] + w + 1;
	for (i = 0; i < n * 2; i++)
		ii[i] = i;
	zz = xx_, sort(ii, 0, n * 2);
	for (i = 0; i < n_ * 2; i++)
		stl[i] = INF, str[i] = -1, stc[i] = 0, kk[i] = 0;
	m = 0;
	ll[m] = INF, rr[m] = -1, cc[m] = INF, xx1[m] = -INF, m++;
	for (h = 0; h < n * 2; h++) {
		i = ii[h];
		if ((i & 1) == 0)
			update(yy[i >> 1], 1);
		else
			update(yy[i >> 1], -1);
		if (h + 1 == n * 2 || xx_[ii[h + 1]] != xx_[ii[h]]) {
			if (stl[1] == INF)
				ll[m] = INF, rr[m] = -1, cc[m] = INF;
			else
				ll[m] = stl[1], rr[m] = str[1], cc[m] = stc[1];
			xx1[m++] = xx_[ii[h]];
		}
	}
	xx1[m] = INF;
	ans = LINF;
	for (x = 0; x <= w; x++) {
		l = -1, r = INF, c = 0;
		for (h = 0; h < m; h++) {
			if (xx1[h + 1] <= x || x + x_ <= xx1[h])
				continue;
			l = max(l, ll[h]), r = min(r, rr[h]), c = max(c, cc[h]);
		}
		if (l != INF && r != -1 && c != INF)
			ans = min(ans, w + max(l + y_ - 1 - r, c));
	}
	return ans;
}

int main() {
	static int ii[N];
	int h, i, j, y;
	long long ans;

	scanf("%d%d%d", &x_, &y_, &n);
	for (i = 0; i < n; i++)
		scanf("%d%d", &xx[i], &yy[i]), xx[i]--, yy[i]--;
	for (i = 0; i < n; i++)
		ii[i] = i;
	zz = yy, sort(ii, 0, n);
	n_ = 0;
	for (h = 0; h < n; h++) {
		i = ii[h], y = yy[i];
		if (n_ == 0 || yy_[n_ - 1] != y)
			yy_[n_++] = y;
		yy[i] = n_ - 1;
	}
	n_ = 1;
	while (n_ < n)
		n_ <<= 1;
	ans = LINF;
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			ans = min(ans, min(solve((x_ - 1 - xx[i]) + (xx[j] - 0)), solve(xx[j] - xx[i] - 1)));
	printf("%lld\n", ans);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

cultivation.c: In function 'main':
cultivation.c:116:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |  scanf("%d%d%d", &x_, &y_, &n);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cultivation.c:118:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |   scanf("%d%d", &xx[i], &yy[i]), xx[i]--, yy[i]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 20
• Subtask 6: 0 / 20