Submission #661149

#	Time	Username	Problem	Language	Result	Execution time	Memory
661149		rainboy	IOI Fever (JOI21_fever)	C11	100 / 100	3167 ms	37552 KiB

fever

#include <stdio.h>

#define N	100000
#define N_	(1 << 17)	/* N_ = pow2(ceil(log2(N))) */
#define INF	0x3f3f3f3f

int min(int a, int 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;
}

int xx[N], yy[N], tt[N], zz[8][N], ii[8][N], pp[8][N], n, n_, hx, hy;

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) {
			int c = zz[hy][ii[j]] != zz[hy][i_] ? zz[hy][ii[j]] - zz[hy][i_] : zz[hx][ii[j]] - zz[hx][i_];

			if (c == 0)
				j++;
			else if (c < 0) {
				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 st[8][N_ * 2], aa[8][N_ * 2], bb[8][N_ * 2];

void pul(int *st, int *aa, int *bb, int i) {
	int l = i << 1, r = l | 1;

	bb[i] = min(bb[l], bb[r]), st[i] = min(st[l], st[r]);
	if (bb[i] != INF && aa[i] != -INF)
		st[i] = min(st[i], bb[i] - aa[i]);
}

void pull(int *st, int *aa, int *bb, int i) {
	while (i > 1)
		pul(st, aa, bb, i >>= 1);
}

void put(int *st, int *aa, int *bb, int i, int x) {
	aa[i] = max(aa[i], x);
	if (bb[i] != INF && aa[i] != -INF)
		st[i] = min(st[i], bb[i] - aa[i]);
}

void update(int *st, int *aa, int *bb, int l, int r, int x) {
	if (l <= r) {
		int l_ = l += n_, r_ = r += n_;

		for ( ; l <= r; l >>= 1, r >>= 1) {
			if ((l & 1) == 1)
				put(st, aa, bb, l++, x);
			if ((r & 1) == 0)
				put(st, aa, bb, r--, x);
		}
		pull(st, aa, bb, l_), pull(st, aa, bb, r_);
	}
}

void upd(int *st, int *aa, int *bb, int i) {
	i += n_, st[i] = bb[i] = INF, aa[i] = -INF, pull(st, aa, bb, i);
}

int query(int *st, int *bb) {
	int i = 1;

	while (i < n_)
		if (st[i] == st[i << 1 | 0])
			i = i << 1 | 0;
		else if (st[i] == st[i << 1 | 1])
			i = i << 1 | 1;
		else
			break;
	while (i < n_)
		i = bb[i] == bb[i << 1 | 0] ? i << 1 | 0 : i << 1 | 1;
	return i - n_;
}

int search(int hx, int x, int y) {
	int hy = (hx + 2) % 8, lower = -1, upper = n;

	while (upper - lower > 1) {
		int i = (lower + upper) / 2;

		if (zz[hy][ii[hx][i]] < y || zz[hy][ii[hx][i]] == y && zz[hx][ii[hx][i]] < x)
			lower = i;
		else
			upper = i;
	}
	return upper;
}

int solve() {
	int h, hl, hr, h_, i, k, d;

	for (i = 0; i < n; i++) {
		zz[0][i] = +xx[i], zz[1][i] = +xx[i] + yy[i];
		zz[2][i] = +yy[i], zz[3][i] = -xx[i] + yy[i];
		zz[4][i] = -xx[i], zz[5][i] = -xx[i] - yy[i];
		zz[6][i] = -yy[i], zz[7][i] = +xx[i] - yy[i];
	}
	n_ = 1;
	while (n_ < n)
		n_ <<= 1;
	for (h = 0; h < 8; h++) {
		for (i = 0; i < n; i++)
			ii[h][i] = i;
		hx = h, hy = (h + 2) % 8, sort(ii[h], 0, n);
		for (i = 0; i < n; i++)
			pp[h][ii[h][i]] = i;
		for (i = 0; i < n_ * 2; i++)
			st[h][i] = INF, aa[h][i] = -INF, bb[h][i] = -INF;
		for (i = 0; i < n; i++)
			bb[h][n_ + i] = zz[hx][ii[h][i]];
		for (i = n_ - 1; i > 0; i--)
			pul(st[h], aa[h], bb[h], i);
	}
	for (i = 0; i < n; i++)
		if (zz[7][i] <= 0 && zz[1][i] <= 0)
			tt[i] = 0;
		else if (zz[7][i] > 0 && zz[1][i] <= 0)
			tt[i] = 1;
		else if (zz[7][i] > 0 && zz[1][i] > 0)
			tt[i] = 2;
		else
			tt[i] = 3;
	for (h = 0; h < 8; h++)
		update(st[h], aa[h], bb[h], pp[h][0], pp[h][0], zz[h][0]);
	k = 0;
	while (1) {
		h_ = -1;
		for (h = 0; h < 8; h++)
			if (st[h][1] != INF && (h_ == -1 || st[h_][1] > st[h][1]))
				h_ = h;
		if (h_ == -1)
			break;
		k++;
		i = ii[h_][query(st[h_], bb[h_])], d = st[h_][1];
		for (h = 0; h < 8; h++)
			upd(st[h], aa[h], bb[h], pp[h][i]);
		if (tt[i] == 0)
			hl = 7, hr = 9;
		else if (tt[i] == 1)
			hl = 1, hr = 3;
		else if (tt[i] == 2)
			hl = 3, hr = 5;
		else
			hl = 5, hr = 7;
		for (h = hl; h <= hr; h++) {
			hx = h % 8, hy = (hx + 2) % 8;
			update(st[hx], aa[hx], bb[hx], search(hx, zz[hx][i] + d, zz[hy][i]), search(hx, INF, zz[hy][i]) - 1, zz[hx][i]);
		}
	}
	return k;
}

int main() {
	int h, i, k_, tmp;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d%d", &xx[i], &yy[i]);
	for (i = 1; i < n; i++)
		xx[i] -= xx[0], yy[i] -= yy[0];
	xx[0] = 0, yy[0] = 0;
	k_ = 0;
	for (h = 0; h < 4; h++) {
		k_ = max(k_, solve());
		for (i = 0; i < n; i++)
			tmp = xx[i], xx[i] = -yy[i], yy[i] = tmp;
	}
	printf("%d\n", k_);
	return 0;
}

Compilation message (stderr)

fever.c: In function 'search':
fever.c:100:55: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  100 |   if (zz[hy][ii[hx][i]] < y || zz[hy][ii[hx][i]] == y && zz[hx][ii[hx][i]] < x)
      |                                ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fever.c: In function 'main':
fever.c:175:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  175 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
fever.c:177:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  177 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 12 / 12
• Subtask 6: 32 / 32
• Subtask 7: 31 / 31