Submission #493520

#	Time	Username	Problem	Language	Result	Execution time	Memory
493520		rainboy	Izvanzemaljci (COI21_izvanzemaljci)	C11	100 / 100	307 ms	11312 KiB

izvanzemaljci

#include <stdio.h>
#include <string.h>
#include <sys/time.h>

#define N	100000
#define INF	0x3f3f3f3f3f3f3f3fLL
#define X	1000000001

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 Z = 12345;

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

int xx[N], yy[N], n;

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

void solve1(int *ii, int n, long long *xx_, long long *yy_, long long *ss_) {
	int i, i_, x, y, xl, xr, yl, yr, s;

	if (n == 0) {
		if (ss_[0] > 1)
			xx_[0] = X + 1, yy_[0] = X + 1, ss_[0] = 1;
		return;
	}
	xl = X, xr = -X, yl = X, yr = -X;
	for (i = 0; i < n; i++) {
		i_ = ii[i], x = xx[i_], y = yy[i_];
		xl = min(xl, x), xr = max(xr, x);
		yl = min(yl, y), yr = max(yr, y);
	}
	s = max(max(xr - xl, yr - yl), 1);
	if (ss_[0] > s)
		xx_[0] = xl, yy_[0] = yl, ss_[0] = s;
}

void solve2(int *ii, int n, long long *xx_, long long *yy_, long long *ss_) {
	static int ypl[N], ypr[N], yql[N], yqr[N];
	int i, xl, xr, xp, xq, y, yl, yr, s;
	long long x0, y0, s0, x1, y1, s1;

	if (n == 0) {
		if (max(ss_[0], ss_[1]) > 1) {
			xx_[0] = -(X + 2), yy_[0] = -(X + 2), ss_[0] = 1;
			xx_[1] = X + 1, yy_[1] = -(X + 2), ss_[1] = 1;
		}
		return;
	}
	xl = xx[ii[0]], xr = xx[ii[n - 1]];
	yl = X, yr = -X;
	for (i = 0; i < n; i++) {
		y = yy[ii[i]];
		ypl[i] = yl = min(yl, y);
		ypr[i] = yr = max(yr, y);
	}
	yl = X, yr = -X;
	for (i = n - 1; i >= 0; i--) {
		y = yy[ii[i]];
		yql[i] = yl = min(yl, y);
		yqr[i] = yr = max(yr, y);
	}
	for (i = -1; i < n; i++) {
		xp = i == -1 ? -(X + 1) : xx[ii[i]], xq = i + 1 == n ? X + 1 : xx[ii[i + 1]];
		if (xp == xq)
			continue;
		if (i == -1)
			s0 = 1, x0 = -(X + 2), y0 = -(X + 2);
		else
			s0 = max(max(xp - xl, ypr[i] - ypl[i]), 1), x0 = xp - s0, y0 = ypr[i] - s0;
		if (i + 1 == n)
			s1 = 1, x1 = X + 1, y1 = -(X + 2);
		else
			s1 = max(max(xr - xq, yqr[i + 1] - yql[i + 1]), 1), x1 = xq, y1 = yqr[i + 1] - s1;
		s = max(s0, s1);
		if (max(ss_[0], ss_[1]) > s) {
			xx_[0] = x0, yy_[0] = y0, ss_[0] = s0;
			xx_[1] = x1, yy_[1] = y1, ss_[1] = s1;
		}
	}
}

void solve21(int *ii, int n, long long *xx_, long long *yy_, long long *ss_) {
	static long long xx1[3], yy1[3], ss1[3];
	static int ii1[N], ii2[N];
	int n1, n2, h, i, i_, lower, upper;

	lower = -X, upper = X;
	while (upper - lower > 1) {
		int y = (lower + upper) / 2;

		n1 = n2 = 0;
		for (i = 0; i < n; i++) {
			i_ = ii[i];
			if (yy[i_] <= y)
				ii1[n1++] = i_;
			else
				ii2[n2++] = i_;
		}
		ss1[0] = ss1[1] = ss1[2] = INF;
		solve2(ii1, n1, xx1, yy1, ss1), solve1(ii2, n2, xx1 + 2, yy1 + 2, ss1 + 2);
		if (max(max(ss_[0], ss_[1]), ss_[2]) > max(max(ss1[0], ss1[1]), ss1[2]))
			for (h = 0; h < 3; h++)
				xx_[h] = xx1[h], yy_[h] = yy1[h], ss_[h] = ss1[h];
		if (max(ss1[0], ss1[1]) < ss1[2])
			lower = y;
		else
			upper = y;
	}
}

int ypl[N], ypr[N], yql[N], yqr[N], ysl[N], ysr[N], ytl[N], ytr[N], xl, xr, xp, xq, xs, xt, yl, yr;
long long x0, y0, s0, x1, y1, s1, x2, y2, s2;

void try(int *ii, int n, int i, int j, long long *xx_, long long *yy_, long long *ss_) {
	xp = i == 0 ? -(X + 1) : xx[ii[i - 1]], xs = xx[ii[i]];
	xt = xx[ii[j]], xq = j + 1 == n ? X + 1 : xx[ii[j + 1]];
	yl = min(ysl[i], ytl[j]), yr = max(ysr[i], ytr[j]);
	if (xp < xs && xt < xq && (i == 0 || j + 1 == n || max(yr - yl, 1) <= xq - xp - 2)) {
		if (i == 0)
			s0 = 1, x0 = -(X + 2), y0 = -(X + 2);
		else
			s0 = max(max(xp - xl, ypr[i - 1] - ypl[i - 1]), 1), x0 = xp - s0, y0 = ypr[i - 1] - s0;
		if (j + 1 == n)
			s2 = 1, x2 = X + 1, y2 = -(X + 2);
		else
			s2 = max(max(xr - xq, yqr[j + 1] - yql[j + 1]), 1), x2 = xq, y2 = yqr[j + 1] - s2;
		s1 = max(max(xt - xs, yr - yl), 1), x1 = min(xs, j + 1 == n ? X + 1 : xq - 1 - s1), y1 = yl;
		if (max(max(ss_[0], ss_[1]), ss_[2]) > max(max(s0, s1), s2)) {
			xx_[0] = x0, yy_[0] = y0, ss_[0] = s0;
			xx_[1] = x1, yy_[1] = y1, ss_[1] = s1;
			xx_[2] = x2, yy_[2] = y2, ss_[2] = s2;
		}
	}
}

void update(int *ft, int i, int n, int x) {
	while (i < n) {
		ft[i] = max(ft[i], x);
		i |= i + 1;
	}
}

int query(int *ft, int i) {
	int x = -1;

	while (i >= 0) {
		x = max(x, ft[i]);
		i &= i + 1, i--;
	}
	return x;
}

void solve111(int *ii, int n, long long *xx_, long long *yy_, long long *ss_) {
	static int ii1[N], jj1[N], ii2[N], jj2[N], ii_[N], iil[N], iir[N], jj_[N], jjl[N], jjr[N];
	static int uu[N], vv[N], ft1[N], ft2[N];
	int ni, nj, i, i_, j, j_, y, lower, upper;

	if (n == 0) {
		if (max(max(ss_[0], ss_[1]), ss_[2]) > 1) {
			xx_[0] = -(X + 2), yy_[0] = -(X + 2), ss_[0] = 1;
			xx_[1] = 0, yy_[1] = -(X + 2), ss_[1] = 1;
			xx_[2] = X + 1, yy_[2] = -(X + 2), ss_[2] = 1;
		}
		return;
	}
	xl = xx[ii[0]], xr = xx[ii[n - 1]];
	yl = X, yr = -X;
	for (i = 0; i < n; i++) {
		y = yy[ii[i]];
		ypl[i] = yl = min(yl, y);
		ypr[i] = yr = max(yr, y);
	}
	yl = X, yr = -X;
	for (i = n - 1; i >= 0; i--) {
		y = yy[ii[i]];
		yql[i] = yl = min(yl, y);
		yqr[i] = yr = max(yr, y);
	}
	for (i = 0; i + 1 < n; i++) {
		xp = xx[ii[i]], xq = xx[ii[i + 1]];
		s0 = max(max(xp - xl, ypr[i] - ypl[i]), 1);
		s1 = max(max(xr - xq, yqr[i + 1] - yql[i + 1]), 1);
		if (s0 > s1)
			break;
	}
	i_ = i;
	yl = X, yr = -X;
	ysl[i_] = X, ysr[i_] = -X;
	for (i = i_ - 1; i >= 0; i--) {
		y = yy[ii[i]];
		ysl[i] = yl = min(yl, y);
		ysr[i] = yr = max(yr, y);
	}
	yl = X, yr = -X;
	for (i = i_; i < n; i++) {
		y = yy[ii[i]];
		ytl[i] = yl = min(yl, y);
		ytr[i] = yr = max(yr, y);
	}
	for (i = i_; i >= 0; i--)
		try(ii, n, i, n - 1, xx_, yy_, ss_);
	for (j = i_; j < n; j++) {
		try(ii, n, 0, j, xx_, yy_, ss_);
		try(ii, n, i_, j, xx_, yy_, ss_);
	}
	ni = 0;
	for (i = i_ - 1; i > 0; i--)
		if (xx[ii[i]] > xx[ii[i - 1]])
			ii1[ni++] = i;
	nj = 0;
	for (j = i_; j + 1 < n; j++)
		if (xx[ii[j]] < xx[ii[j + 1]])
			jj1[nj++] = j;
	for (i = 0, j = nj - 1; i < ni; i++) {
		i_ = ii1[i];
		while (j > 0) {
			j_ = jj1[j];
			xp = xx[ii[i_ - 1]], xs = xx[ii[i_]];
			xt = xx[ii[j_]], xq = xx[ii[j_ + 1]];
			yl = min(ysl[i_], ytl[j_]), yr = max(ysr[i_], ytr[j_]);
			s1 = max(max(xt - xs, yr - yl), 1), s2 = max(max(xr - xq, yqr[j_ + 1] - yql[j_ + 1]), 1);
			if (s1 <= s2)
				break;
			j--;
		}
		jj_[i] = j;
	}
	for (i = 0, j = 0; i < ni; i++) {
		i_ = ii1[i];
		while (j < nj && ysl[i_] <= ytl[jj1[j]])
			j++;
		jjl[i] = j;
	}
	for (i = 0, j = 0; i < ni; i++) {
		i_ = ii1[i];
		while (j < nj && ysr[i_] >= ytr[jj1[j]])
			j++;
		jjr[i] = j;
	}
	for (j = 0, i = ni - 1; j < nj; j++) {
		j_ = jj1[j];
		while (i > 0) {
			i_ = ii1[i];
			xp = xx[ii[i_ - 1]], xs = xx[ii[i_]];
			xt = xx[ii[j_]], xq = xx[ii[j_ + 1]];
			yl = min(ysl[i_], ytl[j_]), yr = max(ysr[i_], ytr[j_]);
			s1 = max(max(xt - xs, yr - yl), 1), s0 = max(max(xp - xl, ypr[i_ - 1] - ypl[i_ - 1]), 1);
			if (s1 <= s0)
				break;
			i--;
		}
		ii_[j] = i;
	}
	for (i = 0, j = 0; j < nj; j++) {
		j_ = jj1[j];
		while (i < ni && ytl[j_] <= ysl[ii1[i]])
			i++;
		iil[j] = i;
	}
	for (i = 0, j = 0; j < nj; j++) {
		j_ = jj1[j];
		while (i < ni && ytr[j_] >= ysr[ii1[i]])
			i++;
		iir[j] = i;
	}
	/* ysl[i_] <= ytl[j_] && ysr[i_] >= ytr[j_] */
	for (i = 0; i < ni; i++) {
		i_ = ii1[i];
		lower = -1, upper = min(jjl[i], jjr[i]);
		while (upper - lower > 1) {
			j = (lower + upper) / 2, j_ = jj1[j];
			if (ysr[i_] - ysl[i_] <= xx[ii[j_ + 1]] - xx[ii[i_ - 1]] - 2)
				upper = j;
			else
				lower = j;
		}
		lower = upper, upper = min(jjl[i], jjr[i]) - 1;
		if (lower > upper)
			continue;
		j = jj_[i];
		if (j < lower)
			try(ii, n, i_, jj1[lower], xx_, yy_, ss_);
		else if (j > upper)
			try(ii, n, i_, jj1[upper], xx_, yy_, ss_);
		else
			try(ii, n, i_, jj1[j], xx_, yy_, ss_);
	}
	/* ytl[j_] <= ysl[i_] && ytr[j_] >= ysr[i_] */
	for (j = 0; j < nj; j++) {
		j_ = jj1[j];
		lower = -1, upper = min(iil[j], iir[j]);
		while (upper - lower > 1) {
			i = (lower + upper) / 2, i_ = ii1[i];
			if (ytr[j_] - ytl[j_] <= xx[ii[j_ + 1]] - xx[ii[i_ - 1]] - 2)
				upper = i;
			else
				lower = i;
		}
		lower = upper, upper = min(iil[j], iir[j]) - 1;
		if (lower > upper)
			continue;
		i = ii_[j];
		if (i < lower)
			try(ii, n, ii1[lower], j_, xx_, yy_, ss_);
		else if (i > upper)
			try(ii, n, ii1[upper], j_, xx_, yy_, ss_);
		else
			try(ii, n, ii1[i], j_, xx_, yy_, ss_);
	}
	for (i = 0; i < ni; i++)
		ii2[i] = i;
	for (j = 0; j < nj; j++)
		jj2[j] = j;
	/* ysl[i_] <= ytl[j_] && ysr[i_] < ytr[j_] */
	for (i = 0; i < ni; i++) {
		i_ = ii1[i];
		uu[i] = ysl[i_] - (xx[ii[i_ - 1]] + 1);
	}
	for (j = 0; j < nj; j++) {
		j_ = jj1[j];
		vv[j] = ytr[j_] - (xx[ii[j_ + 1]] - 1);
	}
	zz = uu, sort(ii2, 0, ni);
	zz = vv, sort(jj2, 0, nj);
	memset(ft1, -1, nj * sizeof *ft1);
	memset(ft2, -1, nj * sizeof *ft2);
	for (i = 0, j = 0; i < ni; i++) {
		lower = jjr[i], upper = jjl[i] - 1;
		if (lower > upper)
			continue;
		i_ = ii2[i];
		while (j < nj && uu[i_] >= vv[j_ = jj2[j]])
			update(ft1, j_, nj, j_), update(ft2, nj - 1 - j_, nj, nj - 1 - j_), j++;
		j_ = query(ft1, min(jj_[i_], upper));
		if (j_ >= lower)
			try(ii, n, ii1[i_], jj1[j_], xx_, yy_, ss_);
		j_ = nj - 1 - query(ft2, nj - 1 - max(jj_[i_], lower));
		if (j_ <= upper)
			try(ii, n, ii1[i_], jj1[j_], xx_, yy_, ss_);
	}
	/* ysl[i_] > ytl[j_] && ysr[i_] >= ytr[j_] */
	for (i = 0; i < ni; i++) {
		i_ = ii1[i];
		uu[i] = -(ysr[i_] + (xx[ii[i_ - 1]] + 1));
	}
	for (j = 0; j < nj; j++) {
		j_ = jj1[j];
		vv[j] = -(ytl[j_] + (xx[ii[j_ + 1]] - 1));
	}
	zz = uu, sort(ii2, 0, ni);
	zz = vv, sort(jj2, 0, nj);
	memset(ft1, -1, nj * sizeof *ft1);
	memset(ft2, -1, nj * sizeof *ft2);
	for (i = 0, j = 0; i < ni; i++) {
		lower = jjl[i], upper = jjr[i] - 1;
		if (lower > upper)
			continue;
		i_ = ii2[i];
		while (j < nj && uu[i_] >= vv[j_ = jj2[j]])
			update(ft1, j_, nj, j_), update(ft2, nj - 1 - j_, nj, nj - 1 - j_), j++;
		j_ = query(ft1, min(jj_[i_], upper));
		if (j_ >= lower)
			try(ii, n, ii1[i_], jj1[j_], xx_, yy_, ss_);
		j_ = nj - 1 - query(ft2, nj - 1 - max(jj_[i_], lower));
		if (j_ <= upper)
			try(ii, n, ii1[i_], jj1[j_], xx_, yy_, ss_);
	}
}

int main() {
	static int ii[N];
	static long long xx_[3], yy_[3], ss_[3];
	int k, h, i, r;
	long long tmp;

	scanf("%d%d", &n, &k);
	for (i = 0; i < n; i++) {
		scanf("%d%d", &xx[i], &yy[i]);
		ii[i] = i;
	}
	ss_[0] = INF;
	if (k == 1)
		solve1(ii, n, xx_, yy_, ss_);
	else if (k == 2)
		for (r = 0; r < 2; r++) {
			zz = xx, sort(ii, 0, n);
			solve2(ii, n, xx_, yy_, ss_);
			for (i = 0; i < n; i++)
				tmp = xx[i], xx[i] = yy[i], yy[i] = tmp;
			for (h = 0; h < k; h++)
				tmp = xx_[h], xx_[h] = yy_[h], yy_[h] = tmp;
		}
	else if (k == 3) {
		for (r = 0; r < 4; r++) {
			zz = xx, sort(ii, 0, n);
			solve21(ii, n, xx_, yy_, ss_);
			for (i = 0; i < n; i++)
				tmp = xx[i], xx[i] = -yy[i], yy[i] = tmp;
			for (h = 0; h < k; h++)
				tmp = xx_[h], xx_[h] = -yy_[h], yy_[h] = tmp, xx_[h] -= ss_[h];
		}
		for (r = 0; r < 2; r++) {
			zz = xx, sort(ii, 0, n);
			solve111(ii, n, xx_, yy_, ss_);
			for (i = 0; i < n; i++)
				tmp = xx[i], xx[i] = yy[i], yy[i] = tmp;
			for (h = 0; h < k; h++)
				tmp = xx_[h], xx_[h] = yy_[h], yy_[h] = tmp;
		}
	}
	for (h = 0; h < k; h++)
		printf("%lld %lld %lld\n", xx_[h], yy_[h], ss_[h]);
	return 0;
}

Compilation message (stderr)

izvanzemaljci.c:135:15: warning: built-in function 'y0' declared as non-function [-Wbuiltin-declaration-mismatch]
  135 | long long x0, y0, s0, x1, y1, s1, x2, y2, s2;
      |               ^~
izvanzemaljci.c:135:27: warning: built-in function 'y1' declared as non-function [-Wbuiltin-declaration-mismatch]
  135 | long long x0, y0, s0, x1, y1, s1, x2, y2, s2;
      |                           ^~
izvanzemaljci.c: In function 'main':
izvanzemaljci.c:399:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  399 |  scanf("%d%d", &n, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~
izvanzemaljci.c:401:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  401 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 21 / 21
• Subtask 3: 12 / 12
• Subtask 4: 30 / 30
• Subtask 5: 32 / 32