Submission #683158

#	Time	Username	Problem	Language	Result	Execution time	Memory
683158		rainboy	Cultivation (JOI17_cultivation)	C11	55 / 100	2070 ms	468 KiB

cultivation

#include <stdio.h>
#include <string.h>

#define N	600
#define N_	(1 << 10)	/* N_ = pow2(ceil(log2(N))) */
#define N2	(N * 2 + 5)
#define INF	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;
}

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

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

long long stl[N_ * 2], str[N_ * 2], stc[N_ * 2]; int 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(long long w) {
	static int ii[N2];
	static long long ll[N2], rr[N2], cc[N2], xx1[N2];
	static int qul[N2], qur[N2], quc[N2];
	int m, h, h_, i, headl, cntl, headr, cntr, headc, cntc;
	long long l, r, c, ans;

	if (w < 0)
		return INF;
	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);
	memset(stl, 0x3f, n_ * 2 * sizeof *stl);
	memset(str, -1, n_ * 2 * sizeof *str);
	memset(stc, 0, n_ * 2 * sizeof *stc);
	memset(kk, 0, n_ * 2 * sizeof *kk);
	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 = INF;
	l = -1, r = INF, c = 0;
	for (h = 0; h < m; h++) {
		if (xx1[h + 1] <= 0 || 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));
	l = -1, r = INF, c = 0;
	for (h = 0; h < m; h++) {
		if (xx1[h + 1] <= w || w + 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));
	headl = cntl = 0, headr = cntr = 0, headc = cntc = 0;
	for (h = 0, h_ = 0; h < m; h++) {
		while (h_ < m && xx1[h_] < xx1[h] + x_) {
			while (cntl && ll[qul[headl + cntl - 1]] <= ll[h_])
				cntl--;
			qul[headl + cntl++] = h_;
			while (cntr && rr[qur[headr + cntr - 1]] >= rr[h_])
				cntr--;
			qur[headr + cntr++] = h_;
			while (cntc && cc[quc[headc + cntc - 1]] <= cc[h_])
				cntc--;
			quc[headc + cntc++] = h_;
			h_++;
		}
		if (xx1[h] >= 0 && xx1[h] <= w) {
			l = ll[qul[headl]], r = rr[qur[headr]], c = cc[quc[headc]];
			if (l != INF && r != -1 && c != INF)
				ans = min(ans, w + max(l + y_ - 1 - r, c));
		}
		if (qul[headl] == h)
			headl++, cntl--;
		if (qur[headr] == h)
			headr++, cntr--;
		if (quc[headc] == h)
			headc++, cntc--;
	}
	return ans;
}

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

	scanf("%lld%lld%d", &x_, &y_, &n);
	for (i = 0; i < n; i++)
		scanf("%lld%lld", &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 = INF;
	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;
}

Compilation message (stderr)

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

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