oj.uz

Submission #819807

# Submission time Handle Problem Language Result Execution time Memory
819807 2023-08-10T13:45:11 Z rainboy Cell Automaton (JOI23_cell) C
33 / 100
 836 ms 21620 KB 
#include <stdio.h>

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

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[M1]; long long cc1[M1]; int hh1[M1], 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_function(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 ((x + y) % 2 != 0)
		return;
	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 ((x1 + y) % 2 != 0)
		x1--;
	if ((x2 + y) % 2 != 0)
		x2++;
	if (x1 >= x2)
		return;
	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]++;
	}
}

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_;
		} else
			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 get_events() {
	int h, h_, i, j, o, ol, or, tmp, corner;
	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 (ol = 0; ol < eo[i]; ol++) {
				j = ej[i][ol], t = dist(i, j);
				or = ol + 1;
				while (or < eo[i] && dist(i, ej[i][or]) == t)
					or++;
				corner = 0;
				for (o = ol; o < or; o++) {
					j = ej[i][o];
					if (ul != -INF && ur != INF && t >= ur - ul) {
						add_function(ur - ul, 1, ul - ur);
						if ((ur - ul) % 2 == 0)
							add_vertex((ur - ul) / 2, (ul + ur) / 2, vv[i] + (ur - ul) / 2);
						goto out;
					}
					if (vv[i] <= vv[j] && xx[i] > xx[j]) {
						if (ul == -INF)
							add_function(t, -1, t), ul = uu[j];
					} else if (yy[i] >= yy[j] && vv[i] < vv[j]) {
						if (ur == INF)
							add_function(t, -1, t), ur = uu[j];
						if (corner == 0 && i < j && yy[i] == yy[j])
							corner = 1;
						else
							corner = -1;
					} else if (xx[i] <= xx[j] && uu[i] > uu[j]) {
						if (ul == -INF) {
							if (ur != INF && t >= ur - uu[j]) {
								add_function(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);
								}
								goto out;
							} else {
								add_function(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_function(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);
								}
								goto out;
							} else if (ul < uu[j]) {
								add_function(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_function(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);
								}
								goto out;
							} else {
								add_function(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_function(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);
								}
								goto out;
							} else if (ur > uu[j]) {
								add_function(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 (t % 2 == 0 && corner == 1 && ul < uu[i] + t && ur == uu[i] + t)
					tt1[m1] = t / 2, cc1[m1] = -1, m1++;
			}
out:
			if (o == eo[i] && ul != -INF && ur != INF) {
				add_function(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);
	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++;
	}
	for (h = 0; h < m1; h++)
		hh1[h] = h;
	compare = compare_t1, sort(hh1, 0, 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();
		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 < m1 && tt1[hh1[h1]] < t)
					h1++;
				ans = (a * t * 2 + b) / 2;
				while (h1 < m1 && tt1[hh1[h1]] == t)
					ans += cc1[hh1[h1++]];
			}
			printf("%lld\n", ans);
		}
	}
	return 0;
}

Compilation message

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

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 1852 KB Output is correct
2 Correct 49 ms 1852 KB Output is correct
3 Correct 46 ms 1740 KB Output is correct
4 Correct 46 ms 1852 KB Output is correct
5 Correct 55 ms 1740 KB Output is correct
6 Correct 47 ms 1856 KB Output is correct
7 Correct 46 ms 1852 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 179 ms 8400 KB Output is correct
11 Correct 48 ms 1856 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 1852 KB Output is correct
2 Correct 49 ms 1852 KB Output is correct
3 Correct 46 ms 1740 KB Output is correct
4 Correct 46 ms 1852 KB Output is correct
5 Correct 55 ms 1740 KB Output is correct
6 Correct 47 ms 1856 KB Output is correct
7 Correct 46 ms 1852 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 179 ms 8400 KB Output is correct
11 Correct 48 ms 1856 KB Output is correct
12 Correct 184 ms 7308 KB Output is correct
13 Correct 149 ms 7344 KB Output is correct
14 Correct 156 ms 7328 KB Output is correct
15 Correct 150 ms 7376 KB Output is correct
16 Correct 94 ms 3980 KB Output is correct
17 Correct 99 ms 4112 KB Output is correct
18 Correct 105 ms 6272 KB Output is correct
19 Correct 155 ms 7288 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 714 ms 16484 KB Output is correct
2 Correct 717 ms 16492 KB Output is correct
3 Correct 606 ms 16992 KB Output is correct
4 Correct 607 ms 16996 KB Output is correct

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 714 ms 16484 KB Output is correct
2 Correct 717 ms 16492 KB Output is correct
3 Correct 606 ms 16992 KB Output is correct
4 Correct 607 ms 16996 KB Output is correct
5 Incorrect 836 ms 21620 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -