Submission #926840

#	Time	Username	Problem	Language	Result	Execution time	Memory
926840		rainboy	Cell Automaton (JOI23_cell)	C11	74 / 100	975 ms	148792 KiB

cell

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

#define N	100000
#define N_	2000
#define Q	500000
#define X	2000
#define T	1000
#define INF	0x7fffffff

long long abs_(long long a) { return a > 0 ? a : -a; }
int min(int a, int 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 tt[Q]; long long ans[Q]; int q;

int compare_x(int i, int j) {
	return xx[i] - xx[j];
}

int tt_[N];

int compare_t_(int i, int j) {
	return tt_[i] != tt_[j] ? (tt_[i] < tt_[j] ? -1 : 1) : 0;
}

int (*compare)(int, int);

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 = compare(ii[j], 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;
	}
}

void solve2() {
	static int dd[X * 2 + 1][X * 2 + 1], nn[T + 1];
	int h, i, x, y;

	for (x = 0; x <= X * 2; x++)
		for (y = 0; y <= X * 2; y++)
			dd[x][y] = T + 1;
	for (i = 0; i < n; i++)
		dd[X + xx[i]][X + yy[i]] = 0;
	for (x = 0; x <= X * 2; x++) {
		for (y = 1; y <= X * 2; y++)
			dd[x][y] = min(dd[x][y], dd[x][y - 1] + 1);
		for (y = X * 2 - 1; y >= 0; y--)
			dd[x][y] = min(dd[x][y], dd[x][y + 1] + 1);
	}
	for (y = 0; y <= X * 2; y++) {
		for (x = 1; x <= X * 2; x++)
			dd[x][y] = min(dd[x][y], dd[x - 1][y] + 1);
		for (x = X * 2 - 1; x >= 0; x--)
			dd[x][y] = min(dd[x][y], dd[x + 1][y] + 1);
	}
	memset(nn, 0, (T + 1) * sizeof *nn);
	for (x = 0; x <= X * 2; x++)
		for (y = 0; y <= X * 2; y++)
			if (dd[x][y] <= T)
				nn[dd[x][y]]++;
	for (h = 0; h < q; h++)
		ans[h] = nn[tt[h]];
}

void solve4() {
	static int ii[N];
	int h, i, i_, a;
	long long b, t;

	for (i = 0; i < n; i++)
		ii[i] = i;
	compare = compare_x, sort(ii, 0, n);
	for (i = 0; i + 1 < n; i++) {
		tt_[i] = xx[ii[i + 1]] - xx[ii[i]];
		ii[i] = i;
	}
	compare = compare_t_, sort(ii, 0, n - 1);
	i = 0, a = n * 4, b = 0;
	for (h = 0; h < q; h++) {
		t = tt[h];
		if (t == 0) {
			ans[h] = n;
			continue;
		}
		while (i < n - 1 && tt_[i_ = ii[i]] < t) {
			a -= 4, b += (long long) tt_[i_] * 2;
			i++;
		}
		ans[h] = 0;
		while (i < n - 1 && tt_[i_ = ii[i]] == t) {
			ans[h] += t - 1;
			a -= 4, b += (long long) tt_[i_] * 2;
			i++;
		}
		ans[h] += (long long) a * t + b;
	}
}

long long uu[N], vv[N];
int aa[Q + 1]; long long bb[Q + 1];

void add(int t, int a, long long b) {
	int lower = -1, upper = q;

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

		if (tt[h] >= t)
			upper = h;
		else
			lower = h;
	}
	aa[upper] += a, bb[upper] += b;
}

void solve6() {
	static int jj[N];
	int cnt, h, i, j, r, t, tmp;
	long long u, u_, ul, ur;

	for (i = 0; i < n; i++)
		uu[i] = xx[i] - yy[i], vv[i] = xx[i] + yy[i];
	memset(aa, 0, (q + 1) * sizeof *aa), memset(bb, 0, (q + 1) * sizeof *bb);
	for (r = 0; r < 4; r++) {
		for (i = 0; i < n; i++) {
			cnt = 0;
			for (j = 0; j < n; j++)
				if (j != i) {
					if (vv[i] > vv[j] || vv[i] == vv[j] && i < j)
						continue;
					tt_[j] = (max(abs_(uu[i] - uu[j]), abs_(vv[i] - vv[j])) + (i < j ? 2 : 1)) / 2;
					jj[cnt++] = j;
				}
			compare = compare_t_, sort(jj, 0, cnt);
			add(0, 1, 0);
			u = uu[i], ul = -INF, ur = INF, t = INF;
			for (h = 0; h <= cnt; h++) {
				if (h == cnt) {
					t = ul != -INF && ur != INF ? (ur - ul) / 2 + 1 : INF;
					break;
				}
				j = jj[h], t = tt_[j];
				if (ul != -INF && ur != INF && ul + t > ur - t) {
					t = (ur - ul) / 2 + 1;
					break;
				}
				if (uu[j] < u) {
					u_ = uu[j] + (i < j ? 0 : 1);
					if (ul == -INF)
						ul = u_, add(t, -1, (u - u_) / 2);
					else if (ul < u_)
						add(t, 0, (u - u_) / 2 - (u - ul) / 2), ul = u_;
				} else {
					u_ = uu[j] - (i < j ? 0 : 1);
					if (ur == INF)
						ur = u_, add(t, -1, (u_ - u + 2) / 2);
					else if (ur > u_)
						add(t, 0, (u_ - u + 2) / 2 - (ur - u + 2) / 2), ur = u_;
				}
				if (ul != -INF && ur != INF && ul + t > ur - t)
					break;
			}
			if (t != INF)
				add(t, 1, -((u - ul) / 2 + (ur - u + 2) / 2));
		}
		for (i = 0; i < n; i++) {
			tmp = xx[i], xx[i] = -yy[i], yy[i] = tmp;
			tmp = uu[i], uu[i] = -vv[i], vv[i] = tmp;
		}
	}
	for (h = 1; h < q; h++)
		aa[h] += aa[h - 1], bb[h] += bb[h - 1];
	for (h = 0; h < q; h++)
		ans[h] = tt[h] == 0 ? n : (long long) aa[h] * tt[h] + bb[h];
}

void test() {
	static long long ans_[Q];
	int h;

	solve2(), memcpy(ans_, ans, q * sizeof *ans), solve6();
	for (h = 0; h < q; h++)
		if (ans[h] != ans_[h]) {
			printf("wrong answer on query %d: expected %lld, found %lld\n", h + 1, ans_[h], ans[h]);
			exit(0);
		}
}

void stress() {
	int t, h, i, j;

	for (t = 1; t <= T; t++) {
		printf("running on test %d...\n", t);
generate:
		n = 10, q = T + 1;
		for (i = 0; i < n; i++)
			xx[i] = rand_() % 2001 - 1000, yy[i] = rand_() % 2001 - 1000;
		for (i = 0; i < n; i++)
			for (j = i + 1; j < n; j++)
				if (xx[j] == xx[i] && yy[j] == yy[i])
					goto generate;
		for (h = 0; h < q; h++)
			tt[h] = h;
		test();
	}
	printf("AC\n");
}

int main() {
	int h, i, subtask;

	scanf("%d%d", &n, &q);
	for (i = 0; i < n; i++)
		scanf("%d%d", &xx[i], &yy[i]);
	for (h = 0; h < q; h++)
		scanf("%d", &tt[h]);
#if 0
	stress();
#endif
	if (n <= N_)
		subtask = 6;
	else {
		subtask = 4;
		for (i = 0; i < n; i++)
			if (xx[i] != yy[i]) {
				subtask = 2;
				break;
			}
	}
	if (subtask == 2)
		solve2();
	else if (subtask == 4)
		solve4();
	else if (subtask == 6)
		solve6();
	for (h = 0; h < q; h++)
		printf("%lld\n", ans[h]);
	return 0;
}

Compilation message (stderr)

cell.c: In function 'solve6':
cell.c:153:42: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  153 |      if (vv[i] > vv[j] || vv[i] == vv[j] && i < j)
      |                           ~~~~~~~~~~~~~~~^~~~~~~~
cell.c: In function 'main':
cell.c:236:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  236 |  scanf("%d%d", &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~
cell.c:238:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  238 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cell.c:240:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  240 |   scanf("%d", &tt[h]);
      |   ^~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 8 / 8
• Subtask 4: 8 / 8
• Subtask 5: 17 / 17
• Subtask 6: 25 / 25
• Subtask 7: 0 / 26