Submission #819485

#	Time	Username	Problem	Language	Result	Execution time	Memory
819485		rainboy	Cell Automaton (JOI23_cell)	C11	33 / 100	745 ms	21896 KiB

cell

#include <stdio.h>

#define N	100000
#define SMALL	2000
#define M	(SMALL * 15)
#define MV	(N * 4)
#define ME	M
#define M_	(MV + ME * 2)
#define X	2000
#define T	1000
#define INF	0x3f3f3f3f

int min(int a, int b) { return a < b ? a : b; }
int abs_(int a) { return a > 0 ? a : -a; }

unsigned int Z = 12345;

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

int xx[N], yy[N], n; long long uu[N], vv[N];

int ej[SMALL][SMALL], eo[SMALL];

int r;
long long tt[M]; int aa[M]; long long bb[M]; int hh[M], m;
int ttv[MV], xxv[MV], yyv[MV], mv;
int tte[2][ME], xxe[2][ME * 2], yye[2][ME], mme[2];
int tt_[M_], xx_[M_], yy_[M_], ww_[M_], hh_[M_], m_;
int tt1[M]; long long cc1[M]; int m1;

int compare_x(int i, int j) {
	return xx[i] == xx[j] ? 0 : (xx[i] < xx[j] ? -1 : 1);
}

int compare_t1(int i, int j) {
	return tt1[i] == tt1[j] ? 0 : (tt1[i] < tt1[j] ? -1 : 1);
}

long long dist(int i, int j) {
	return (long long) abs_(xx[j] - xx[i]) + abs_(yy[j] - yy[i]);
}

int i1;

int compare_d(int i, int j) {
	long long di = dist(i1, i), dj = dist(i1, j);

	return di == dj ? 0 : di < dj ? -1 : 1;
}

int compare_t(int h1, int h2) {
	return tt[h1] == tt[h2] ? 0 : (tt[h1] < tt[h2] ? -1 : 1);
}

int compare_t_(int h1, int h2) {
	return tt_[h1] == tt_[h2] ? 0 : (tt_[h1] < tt_[h2] ? -1 : 1);
}

int compare_yxw(int h1, int h2) {
	if (yy_[h1] != yy_[h2])
		return yy_[h1] < yy_[h2] ? -1 : 1;
	if (xx_[h1] != xx_[h2])
		return xx_[h1] < xx_[h2] ? -1 : 1;
	if (ww_[h1] != ww_[h2])
		return ww_[h1] < ww_[h2] ? -1 : 1;
	return 0;
}

int compare_xyw(int h1, int h2) {
	if (xx_[h1] != xx_[h2])
		return xx_[h1] < xx_[h2] ? -1 : 1;
	if (yy_[h1] != yy_[h2])
		return yy_[h1] < yy_[h2] ? -1 : 1;
	if (ww_[h1] != ww_[h2])
		return ww_[h1] < ww_[h2] ? -1 : 1;
	return 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 get_neighbors() {
	int i, j;

	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			if (j != i)
				ej[i][eo[i]++] = j;
	for (i = 0; i < n; i++)
		compare = compare_d, i1 = i, sort(ej[i], 0, eo[i]);
}

void add_func(long long t, int a, long long b) {
	tt[m] = t, aa[m] = a, bb[m] = b, m++;
}

void add_vertex(int t, int x, int y) {
	if (r == 0)
		ttv[mv] = t, xxv[mv] = x, yyv[mv] = y, mv++;
	else if (r == 1)
		ttv[mv] = t, xxv[mv] = y, yyv[mv] = -x, mv++;
	else if (r == 2)
		ttv[mv] = t, xxv[mv] = -x, yyv[mv] = -y, mv++;
	else
		ttv[mv] = t, xxv[mv] = -y, yyv[mv] = x, mv++;
}

void add_edge(int t, int x1, int x2, int y) {
	if (r == 0) {
		tte[0][mme[0]] = t;
		xxe[0][mme[0] << 1 | 0] = x1, xxe[0][mme[0] << 1 | 1] = x2;
		yye[0][mme[0]] = y;
		mme[0]++;
	} else if (r == 1) {
		tte[1][mme[1]] = t;
		xxe[1][mme[1] << 1 | 0] = -x2, xxe[1][mme[1] << 1 | 1] = -x1;
		yye[1][mme[1]] = y;
		mme[1]++;
	} else if (r == 2) {
		tte[0][mme[0]] = t;
		xxe[0][mme[0] << 1 | 0] = -x2, xxe[0][mme[0] << 1 | 1] = -x1;
		yye[0][mme[0]] = -y;
		mme[0]++;
	} else {
		tte[1][mme[1]] = t;
		xxe[1][mme[1] << 1 | 0] = x1, xxe[1][mme[1] << 1 | 1] = x2;
		yye[1][mme[1]] = -y;
		mme[1]++;
	}
}

void get_events() {
	int h, i, j, o, tmp;
	long long t, ul, ur;

	for (r = 0; r < 4; r++) {
		for (i = 0; i < n; i++)
			uu[i] = xx[i] - yy[i], vv[i] = xx[i] + yy[i];
		for (i = 0; i < n; i++) {
			ul = -INF, ur = INF;
			for (o = 0; o < eo[i]; o++) {
				j = ej[i][o], t = dist(i, j);
				if (ul != -INF && ur != INF && t >= ur - ul) {
					add_func(ur - ul, 1, ul - ur);
					if ((ur - ul) % 2 == 0)
						add_vertex((ur - ul) / 2, (ul + ur) / 2, vv[i] + (ur - ul) / 2);
					break;
				}
				if (vv[i] <= vv[j] && xx[i] > xx[j]) {
					if (ul == -INF)
						add_func(t, -1, t), ul = uu[j];
				} else if (yy[i] >= yy[j] && vv[i] < vv[j]) {
					if (ur == INF)
						add_func(t, -1, t), ur = uu[j];
				} else if (xx[i] <= xx[j] && uu[i] > uu[j]) {
					if (ul == -INF) {
						if (ur != INF && t >= ur - uu[j]) {
							add_func(t, 0, uu[i] - ur);
							if (t % 2 == 0) {
								add_vertex(t / 2, ur - t / 2, vv[i] + t / 2);
								add_edge(t / 2, uu[i] - t / 2, ur - t / 2, vv[i] + t / 2);
							}
							break;
						} else {
							add_func(t, -1, uu[i] - uu[j]);
							if (t % 2 == 0)
								add_edge(t / 2, uu[i] - t / 2, uu[j] + t / 2, vv[i] + t / 2);
							ul = uu[j];
						}
					} else {
						if (ur != INF && t >= ur - uu[j]) {
							add_func(t, 1, ul - ur);
							if (t % 2 == 0) {
								add_vertex(t / 2, ur - t / 2, vv[i] + t / 2);
								add_edge(t / 2, ul + t / 2, ur - t / 2, vv[i] + t / 2);
							}
							break;
						} else if (ul < uu[j]) {
							add_func(t, 0, ul - uu[j]);
							if (t % 2 == 0)
								add_edge(t / 2, ul + t / 2, uu[j] + t / 2, vv[i] + t / 2);
							ul = uu[j];
						}
					}
				} else if (uu[i] <= uu[j] && yy[i] < yy[j]) {
					if (ur == INF) {
						if (ul != -INF && t >= uu[j] - ul) {
							add_func(t, 0, ul - uu[i]);
							if (t % 2 == 0) {
								add_vertex(t / 2, ul + t / 2, vv[i] + t / 2);
								add_edge(t / 2, ul + t / 2, uu[i] + t / 2, vv[i] + t / 2);
							}
							break;
						} else {
							add_func(t, -1, uu[j] - uu[i]);
							if (t % 2 == 0)
								add_edge(t / 2, uu[j] - t / 2, uu[i] + t / 2, vv[i] + t / 2);
							ur = uu[j];
						}
					} else {
						if (ul != -INF && t >= uu[j] - ul) {
							add_func(t, 1, ul - ur);
							if (t % 2 == 0) {
								add_vertex(t / 2, ul + t / 2, vv[i] + t / 2);
								add_edge(t / 2, ul + t / 2, ur - t / 2, vv[i] + t / 2);
							}
							break;
						} else if (ur > uu[j]) {
							add_func(t, 0, uu[j] - ur);
							if (t % 2 == 0)
								add_edge(t / 2, uu[j] - t / 2, ur - t / 2, vv[i] + t / 2);
							ur = uu[j];
						}
					}
				}
			}
			if (o == eo[i] && ul != -INF && ur != INF) {
				add_func(ur - ul, 1, ul - ur);
				if ((ur - ul) % 2 == 0)
					add_vertex((ur - ul) / 2, (ul + ur) / 2, vv[i] + (ur - ul) / 2);
			}
		}
		for (i = 0; i < n; i++)
			tmp = xx[i], xx[i] = -yy[i], yy[i] = tmp;
	}
	for (h = 0; h < m; h++)
		hh[h] = h;
	compare = compare_t, sort(hh, 0, m);
}

long long count_points(int *hh, int m) {
	long long c;
	int m_, h, h_, d, x_, y_;

	c = 0;
	compare = compare_yxw, sort(hh, 0, m);
	m_ = 0, d = 0, x_ = 0;
	for (h = 0; h < m; h++) {
		h_ = hh[h];
		if (ww_[h_] == 1) {
			hh[m_++] = h_;
			if (d++ == 0)
				x_ = xx_[h_];
		} else if (ww_[h_] == -1) {
			hh[m_++] = h_;
			if (--d == 0)
				c += ((long long) xx_[h_] - x_) / 2 - 1;
		} else if (ww_[h_] == 0)
			if (d == 0)
				hh[m_++] = h_;
	}
	m = m_;
	compare = compare_xyw, sort(hh, 0, m);
	m_ = 0, d = 0, y_ = 0;
	for (h = 0; h < m; h++) {
		h_ = hh[h];
		if (ww_[h_] == 2) {
			if (d++ == 0)
				y_ = yy_[h_];
		} else if (ww_[h_] == -2) {
			if (--d == 0)
				c += ((long long) yy_[h_] - y_) / 2 - 1;
		} else if (ww_[h_] == 0)
			if (d == 0)
				hh[m_++] = h_;
	}
	m = m_;
	for (h = 0; h < m; h++)
		if (h == 0 || xx_[hh[h]] != xx_[hh[h - 1]] || yy_[hh[h]] != yy_[hh[h - 1]])
			c++;
	return c;
}

void calc_extra() {
	int h, h_;
	long long t;

	for (h = 0; h < mv; h++)
		tt_[m_] = ttv[h], xx_[m_] = xxv[h], yy_[m_] = yyv[h], ww_[m_] = 0, m_++;
	for (h = 0; h < mme[0]; h++)
		if (xxe[0][h << 1 | 0] != xxe[0][h << 1 | 1]) {
			tt_[m_] = tte[0][h], xx_[m_] = xxe[0][h << 1 | 0], yy_[m_] = yye[0][h], ww_[m_] = 1, m_++;
			tt_[m_] = tte[0][h], xx_[m_] = xxe[0][h << 1 | 1], yy_[m_] = yye[0][h], ww_[m_] = -1, m_++;
		}
	for (h = 0; h < mme[1]; h++)
		if (xxe[1][h << 1 | 0] != xxe[1][h << 1 | 1]) {
			tt_[m_] = tte[1][h], xx_[m_] = yye[1][h], yy_[m_] = xxe[1][h << 1 | 0], ww_[m_] = 2, m_++;
			tt_[m_] = tte[1][h], xx_[m_] = yye[1][h], yy_[m_] = xxe[1][h << 1 | 1], ww_[m_] = -2, m_++;
		}
	for (h = 0; h < m_; h++)
		hh_[h] = h;
	compare = compare_t_, sort(hh_, 0, m_);
	for (h = 0; h < m_; h = h_) {
		t = tt_[hh_[h]], h_ = h + 1;
		while (h_ < m_ && tt_[hh_[h_]] == t)
			h_++;
		tt1[m1] = t, cc1[m1] = count_points(hh_ + h, h_ - h), m1++;
	}
}

int main() {
	int q, subtask, h, h1, i, x, y, a;
	long long t, b, ans;

	scanf("%d%d", &n, &q);
	for (i = 0; i < n; i++)
		scanf("%d%d", &xx[i], &yy[i]);
	if (n <= 2000)
		subtask = 6;
	else {
		subtask = 4;
		for (i = 0; i < n; i++)
			if (xx[i] != yy[i]) {
				subtask = 2;
				break;
			}
	}
	if (subtask == 2) {
		static int dd[X * 2 + 1][X * 2 + 1], nn[T + 1];

		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);
		}
		for (x = 0; x <= X * 2; x++)
			for (y = 0; y <= X * 2; y++)
				if (dd[x][y] <= T)
					nn[dd[x][y]]++;
		while (q--) {
			scanf("%lld", &t);
			printf("%d\n", nn[t]);
		}
	} else if (subtask == 4) {
		static int ii[N];
		int i_;

		for (i = 0; i < n; i++)
			ii[i] = i;
		compare = compare_x, sort(ii, 0, n);
		for (i = 0; i + 1 < n; i++) {
			tt1[i] = xx[ii[i + 1]] - xx[ii[i]];
			ii[i] = i;
		}
		compare = compare_t1, sort(ii, 0, n - 1);
		i = 0, a = n * 4, b = 0;
		while (q--) {
			long long ans;

			scanf("%lld", &t);
			if (t == 0)
				printf("%d\n", n);
			else {
				while (i < n - 1 && tt1[i_ = ii[i]] < t) {
					a -= 4, b += (long long) tt1[i_] * 2;
					i++;
				}
				ans = 0;
				while (i < n - 1 && tt1[i_ = ii[i]] == t) {
					ans += t - 1;
					a -= 4, b += (long long) tt1[i_] * 2;
					i++;
				}
				ans += a * t + b;
				printf("%lld\n", ans);
			}
		}
	} else {
		get_neighbors();
		get_events();
		calc_extra();
		h = 0, h1 = 0, a = n * 4, b = 0;
		while (q--) {
			scanf("%lld", &t);
			if (t == 0)
				ans = n;
			else {
				while (h < m && tt[hh[h]] <= t * 2)
					a += aa[hh[h]], b += bb[hh[h]], h++;
				while (h1 < m && tt1[h1] < t)
					h1++;
				ans = ((long long) a * t * 2 + b) / 2;
				if (h1 < m && tt1[h1] == t)
					ans += cc1[h1];
			}
			printf("%lld\n", ans);
		}
	}
	return 0;
}

Compilation message (stderr)

cell.c: In function 'main':
cell.c:328:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  328 |  scanf("%d%d", &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~
cell.c:330:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  330 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cell.c:366:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  366 |    scanf("%lld", &t);
      |    ^~~~~~~~~~~~~~~~~
cell.c:385:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  385 |    scanf("%lld", &t);
      |    ^~~~~~~~~~~~~~~~~
cell.c:409:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  409 |    scanf("%lld", &t);
      |    ^~~~~~~~~~~~~~~~~

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