Submission #684545

#	Time	Username	Problem	Language	Result	Execution time	Memory
684545		rainboy	Cultivation (JOI17_cultivation)	C11	100 / 100	1379 ms	1392 KiB

cultivation

#include <stdio.h>

#define N	300
#define N2	(N * 2)
#define INF	0x3f3f3f3f
#define LINF	0x3f3f3f3f3f3f3f3fLL

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

unsigned int X = 12345;

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

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

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 (xx[ii[j]] == xx[i_])
				j++;
			else if (xx[ii[j]] < xx[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 lll[N][N], rrr[N][N], ccc[N][N];

long long solve(long long w) {
	static int ll[N2], rr[N2], cc[N2], qul[N2], qur[N2], quc[N2];
	static long long xx_[N2];
	int m, h, h_, il, ir, l, r, c, x, headl, cntl, headr, cntr, headc, cntc;
	long long ans;

	if (w < 0)
		return LINF;
	il = 0, ir = 0, m = 0;
	while (il < n || ir < n) {
		x = il == n || ir < n && xx[ir] <= xx[il] + w + 1 ? xx[ir++] : xx[il++] + w + 1;
		if (m == 0 || xx_[m - 1] != x)
			xx_[m++] = x;
		if (il == ir)
			ll[m - 1] = INF, rr[m - 1] = -1, cc[m - 1] = INF;
		else
			ll[m - 1] = lll[il][ir - 1], rr[m - 1] = rrr[il][ir - 1], cc[m - 1] = ccc[il][ir - 1];
	}
	ans = LINF, headl = cntl = 0, headr = cntr = 0, headc = cntc = 0;
	for (h = 0, h_ = 0; h < m && xx_[h] <= w; h++) {
		while (h_ < m && xx_[h_] < xx_[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_++;
		}
		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], xx_[N], yy_[N];
	int k, h, i, j, tmp;
	long long 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;
	sort(ii, 0, n);
	for (i = 0; i < n; i++)
		xx_[i] = xx[ii[i]], yy_[i] = yy[ii[i]];
	for (i = 0; i < n; i++)
		xx[i] = xx_[i], yy[i] = yy_[i];
	for (i = 0; i < n; i++) {
		k = 0;
		for (j = i; j < n; j++) {
			ii[k++] = j;
			for (h = k - 1; h > 0 && yy[ii[h]] < yy[ii[h - 1]]; h--)
				tmp = ii[h], ii[h] = ii[h - 1], ii[h - 1] = tmp;
			lll[i][j] = yy[ii[0]], rrr[i][j] = yy[ii[k - 1]];
			for (h = 1; h < k; h++)
				ccc[i][j] = max(ccc[i][j], yy[ii[h]] - yy[ii[h - 1]] - 1);
		}
	}
	ans = LINF;
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			ans = min(ans, min(solve(xx[j] - xx[i] - 1), solve(x_ + xx[j] - xx[i] - 1)));
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

cultivation.c: In function 'solve':
cultivation.c:50:25: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   50 |   x = il == n || ir < n && xx[ir] <= xx[il] + w + 1 ? xx[ir++] : xx[il++] + w + 1;
      |                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
cultivation.c: In function 'main':
cultivation.c:90:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |  scanf("%lld%lld%d", &x_, &y_, &n);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cultivation.c:92:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |   scanf("%lld%lld", &xx[i], &yy[i]), xx[i]--, yy[i]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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