답안 #817193

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
817193	2023-08-09T10:28:08 Z	rainboy	Cell Automaton (JOI23_cell)	C	49 / 100	415 ms	127456 KB

cell

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

#define N	100000
#define N_	(1 << 18)	/* N_ = pow2(ceil(log2(N * 2))) */
#define X	2000
#define T	1000

int min(int a, int b) { return a < b ? a : b; }

unsigned int Z = 12345;

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

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

long long xx_[N * 2], yy_[N * 2]; int hh[N * 2], idx[N * 2], m;

int compare_x(int i, int j) { return xx[i] - xx[j]; }
int compare_t(int i, int j) { return tt[i] - tt[j]; }
int compare_x_(int h1, int h2) { return xx_[h1] != xx_[h2] ? (xx_[h1] < xx_[h2] ? -1 : 1) : 0; }
int compare_y_(int h1, int h2) { return yy_[h1] != yy_[h2] ? (yy_[h1] < yy_[h2] ? -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;
	}
}

long long st[N_ * 2], sz[N_ * 2]; int lz[N_ * 2], n_;

void pul(int i) {
	int l = i << 1, r = l | 1;

	st[i] = lz[i] ? sz[i] : (i >= n_ ? 0 : st[l] + st[r]);
}

void pull(int i) {
	while (i > 1)
		pul(i >>= 1);
}

void update(int l, int r, int x) {
	int l_ = l += n_, r_ = r += n_;

	for ( ; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			lz[l] += x, pul(l++);
		if ((r & 1) == 0)
			lz[r] += x, pul(r--);
	}
	pull(l_), pull(r_);
}

long long solve(int t) {
	int r, h, i;
	long long ans;

	ans = 0;
	for (r = 0; r < 2; r++) {
		m = 0;
		for (i = 0; i < n; i++) {
			xx_[i << 1 | 0] = (long long) xx[i] + yy[i] - t + r;
			xx_[i << 1 | 1] = (long long) xx[i] + yy[i] + t + r;
			yy_[i << 1 | 0] = (long long) xx[i] - yy[i] - t + r;
			yy_[i << 1 | 1] = (long long) xx[i] - yy[i] + t + r;
			if (xx_[i << 1 | 0] % 2 != 0)
				xx_[i << 1 | 0]++;
			if (xx_[i << 1 | 1] % 2 != 0)
				xx_[i << 1 | 1]--;
			if (yy_[i << 1 | 0] % 2 != 0)
				yy_[i << 1 | 0]++;
			if (yy_[i << 1 | 1] % 2 != 0)
				yy_[i << 1 | 1]--;
			if (xx_[i << 1 | 0] > xx_[i << 1 | 1] || yy_[i << 1 | 0] > yy_[i << 1 | 1])
				continue;
			xx_[i << 1 | 0] /= 2, xx_[i << 1 | 1] /= 2;
			yy_[i << 1 | 0] /= 2, yy_[i << 1 | 1] /= 2;
			xx_[i << 1 | 1]++, yy_[i << 1 | 1]++;
			hh[m++] = i << 1 | 0, hh[m++] = i << 1 | 1;
		}
		compare = compare_x_, sort(hh, 0, m);
		n_ = 1;
		while (n_ < m)
			n_ <<= 1;
		for (h = 0; h < m; h++)
			idx[hh[h]] = h;
		memset(st, 0, n_ * 2 * sizeof *st);
		memset(lz, 0, n_ * 2 * sizeof *lz);
		for (i = 0; i < n_; i++)
			sz[n_ + i] = i + 1 < m ? xx_[hh[i + 1]] - xx_[hh[i]] : 0;
		for (i = n_ - 1; i > 0; i--)
			sz[i] = sz[i << 1 | 0] + sz[i << 1 | 1];
		compare = compare_y_, sort(hh, 0, m);
		for (h = 0; h + 1 < m; h++) {
			i = hh[h] >> 1;
			update(idx[i << 1 | 0], idx[i << 1 | 1] - 1, (hh[h] & 1) == 0 ? 1 : -1);
			ans += st[1] * (yy_[hh[h + 1]] - yy_[hh[h]]);
		}
	}
	return ans;
}

int main() {
	static int ii[N], dd[X * 2 + 1][X * 2 + 1], nn[T + 1];
	int q, i, i_, x, y, t, subtask;
	long long a, b;

	scanf("%d%d", &n, &q);
	for (i = 0; i < n; i++)
		scanf("%d%d", &xx[i], &yy[i]);
	if (n <= 2000 && q == 1)
		subtask = 5;
	else {
		subtask = 4;
		for (i = 0; i < n; i++)
			if (xx[i] != yy[i]) {
				subtask = 2;
				break;
			}
	}
	if (subtask == 2) {
		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("%d", &t);
			printf("%d\n", nn[t]);
		}
	} else if (subtask == 4) {
		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;
		while (q--) {
			long long ans;

			scanf("%d", &t);
			if (t == 0)
				printf("%d\n", n);
			else {
				while (i < n - 1 && tt[i_ = ii[i]] < t) {
					a -= 4, b += (long long) tt[i_] * 2;
					i++;
				}
				ans = 0;
				while (i < n - 1 && tt[i_ = ii[i]] == t) {
					ans += t - 1;
					a -= 4, b += (long long) tt[i_] * 2;
					i++;
				}
				ans += a * t + b;
				printf("%lld\n", ans);
			}
		}
	} else {
		while (q--) {
			int t;

			scanf("%d", &t);
			printf("%lld\n", t == 0 ? n : solve(t) - solve(t - 1));
		}
	}
	return 0;
}

Compilation message

cell.c: In function 'main':
cell.c:129:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |  scanf("%d%d", &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~
cell.c:131:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cell.c:165:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |    scanf("%d", &t);
      |    ^~~~~~~~~~~~~~~
cell.c:181:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  181 |    scanf("%d", &t);
      |    ^~~~~~~~~~~~~~~
cell.c:203:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  203 |    scanf("%d", &t);
      |    ^~~~~~~~~~~~~~~

Subtask #1

4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	360 ms	62936 KB	Output is correct
2	Correct	365 ms	62936 KB	Output is correct
3	Correct	370 ms	62956 KB	Output is correct
4	Correct	368 ms	63044 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	359 ms	63020 KB	Output is correct
9	Correct	367 ms	62944 KB	Output is correct
10	Correct	366 ms	62936 KB	Output is correct
11	Correct	369 ms	62952 KB	Output is correct
12	Correct	389 ms	62948 KB	Output is correct
13	Correct	415 ms	62948 KB	Output is correct
14	Correct	393 ms	63052 KB	Output is correct
15	Correct	374 ms	62944 KB	Output is correct
16	Correct	381 ms	62936 KB	Output is correct
17	Correct	378 ms	62940 KB	Output is correct
18	Correct	396 ms	62884 KB	Output is correct
19	Correct	378 ms	62932 KB	Output is correct
20	Correct	389 ms	62940 KB	Output is correct
21	Correct	376 ms	62940 KB	Output is correct
22	Correct	381 ms	62940 KB	Output is correct
23	Correct	376 ms	62932 KB	Output is correct
24	Correct	388 ms	62940 KB	Output is correct
25	Correct	377 ms	62940 KB	Output is correct
26	Correct	374 ms	62940 KB	Output is correct
27	Correct	373 ms	62940 KB	Output is correct
28	Correct	373 ms	62940 KB	Output is correct

Subtask #2

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	360 ms	62936 KB	Output is correct
2	Correct	365 ms	62936 KB	Output is correct
3	Correct	370 ms	62956 KB	Output is correct
4	Correct	368 ms	63044 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	359 ms	63020 KB	Output is correct
9	Correct	367 ms	62944 KB	Output is correct
10	Correct	366 ms	62936 KB	Output is correct
11	Correct	369 ms	62952 KB	Output is correct
12	Correct	389 ms	62948 KB	Output is correct
13	Correct	415 ms	62948 KB	Output is correct
14	Correct	393 ms	63052 KB	Output is correct
15	Correct	374 ms	62944 KB	Output is correct
16	Correct	381 ms	62936 KB	Output is correct
17	Correct	378 ms	62940 KB	Output is correct
18	Correct	396 ms	62884 KB	Output is correct
19	Correct	378 ms	62932 KB	Output is correct
20	Correct	389 ms	62940 KB	Output is correct
21	Correct	376 ms	62940 KB	Output is correct
22	Correct	381 ms	62940 KB	Output is correct
23	Correct	376 ms	62932 KB	Output is correct
24	Correct	388 ms	62940 KB	Output is correct
25	Correct	377 ms	62940 KB	Output is correct
26	Correct	374 ms	62940 KB	Output is correct
27	Correct	373 ms	62940 KB	Output is correct
28	Correct	373 ms	62940 KB	Output is correct
29	Correct	374 ms	62944 KB	Output is correct
30	Correct	376 ms	62940 KB	Output is correct
31	Correct	375 ms	62852 KB	Output is correct
32	Correct	391 ms	63772 KB	Output is correct
33	Correct	1 ms	212 KB	Output is correct
34	Correct	1 ms	212 KB	Output is correct
35	Correct	1 ms	340 KB	Output is correct
36	Correct	374 ms	62940 KB	Output is correct
37	Correct	376 ms	62944 KB	Output is correct
38	Correct	373 ms	62948 KB	Output is correct
39	Correct	383 ms	63020 KB	Output is correct
40	Correct	386 ms	63720 KB	Output is correct

Subtask #3

8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	43 ms	1732 KB	Output is correct
2	Correct	44 ms	1788 KB	Output is correct
3	Correct	44 ms	1848 KB	Output is correct
4	Correct	45 ms	1844 KB	Output is correct
5	Correct	61 ms	1848 KB	Output is correct
6	Correct	44 ms	1744 KB	Output is correct
7	Correct	48 ms	1812 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	3 ms	468 KB	Output is correct
11	Correct	43 ms	1748 KB	Output is correct

Subtask #4

8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	43 ms	1732 KB	Output is correct
2	Correct	44 ms	1788 KB	Output is correct
3	Correct	44 ms	1848 KB	Output is correct
4	Correct	45 ms	1844 KB	Output is correct
5	Correct	61 ms	1848 KB	Output is correct
6	Correct	44 ms	1744 KB	Output is correct
7	Correct	48 ms	1812 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	3 ms	468 KB	Output is correct
11	Correct	43 ms	1748 KB	Output is correct
12	Correct	156 ms	7296 KB	Output is correct
13	Correct	156 ms	7316 KB	Output is correct
14	Correct	153 ms	7284 KB	Output is correct
15	Correct	159 ms	7332 KB	Output is correct
16	Correct	97 ms	3964 KB	Output is correct
17	Correct	107 ms	3924 KB	Output is correct
18	Correct	112 ms	5804 KB	Output is correct
19	Correct	160 ms	7344 KB	Output is correct

Subtask #5

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	596 KB	Output is correct
2	Correct	7 ms	632 KB	Output is correct
3	Correct	9 ms	640 KB	Output is correct
4	Correct	8 ms	596 KB	Output is correct

Subtask #6

0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	596 KB	Output is correct
2	Correct	7 ms	632 KB	Output is correct
3	Correct	9 ms	640 KB	Output is correct
4	Correct	8 ms	596 KB	Output is correct
5	Runtime error	104 ms	127456 KB	Execution killed with signal 11
6	Halted	0 ms	0 KB	-

Subtask #7

0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	360 ms	62936 KB	Output is correct
2	Correct	365 ms	62936 KB	Output is correct
3	Correct	370 ms	62956 KB	Output is correct
4	Correct	368 ms	63044 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	359 ms	63020 KB	Output is correct
9	Correct	367 ms	62944 KB	Output is correct
10	Correct	366 ms	62936 KB	Output is correct
11	Correct	369 ms	62952 KB	Output is correct
12	Correct	389 ms	62948 KB	Output is correct
13	Correct	415 ms	62948 KB	Output is correct
14	Correct	393 ms	63052 KB	Output is correct
15	Correct	374 ms	62944 KB	Output is correct
16	Correct	381 ms	62936 KB	Output is correct
17	Correct	378 ms	62940 KB	Output is correct
18	Correct	396 ms	62884 KB	Output is correct
19	Correct	378 ms	62932 KB	Output is correct
20	Correct	389 ms	62940 KB	Output is correct
21	Correct	376 ms	62940 KB	Output is correct
22	Correct	381 ms	62940 KB	Output is correct
23	Correct	376 ms	62932 KB	Output is correct
24	Correct	388 ms	62940 KB	Output is correct
25	Correct	377 ms	62940 KB	Output is correct
26	Correct	374 ms	62940 KB	Output is correct
27	Correct	373 ms	62940 KB	Output is correct
28	Correct	373 ms	62940 KB	Output is correct
29	Correct	374 ms	62944 KB	Output is correct
30	Correct	376 ms	62940 KB	Output is correct
31	Correct	375 ms	62852 KB	Output is correct
32	Correct	391 ms	63772 KB	Output is correct
33	Correct	1 ms	212 KB	Output is correct
34	Correct	1 ms	212 KB	Output is correct
35	Correct	1 ms	340 KB	Output is correct
36	Correct	374 ms	62940 KB	Output is correct
37	Correct	376 ms	62944 KB	Output is correct
38	Correct	373 ms	62948 KB	Output is correct
39	Correct	383 ms	63020 KB	Output is correct
40	Correct	386 ms	63720 KB	Output is correct
41	Correct	43 ms	1732 KB	Output is correct
42	Correct	44 ms	1788 KB	Output is correct
43	Correct	44 ms	1848 KB	Output is correct
44	Correct	45 ms	1844 KB	Output is correct
45	Correct	61 ms	1848 KB	Output is correct
46	Correct	44 ms	1744 KB	Output is correct
47	Correct	48 ms	1812 KB	Output is correct
48	Correct	0 ms	212 KB	Output is correct
49	Correct	0 ms	212 KB	Output is correct
50	Correct	3 ms	468 KB	Output is correct
51	Correct	43 ms	1748 KB	Output is correct
52	Correct	156 ms	7296 KB	Output is correct
53	Correct	156 ms	7316 KB	Output is correct
54	Correct	153 ms	7284 KB	Output is correct
55	Correct	159 ms	7332 KB	Output is correct
56	Correct	97 ms	3964 KB	Output is correct
57	Correct	107 ms	3924 KB	Output is correct
58	Correct	112 ms	5804 KB	Output is correct
59	Correct	160 ms	7344 KB	Output is correct
60	Correct	6 ms	596 KB	Output is correct
61	Correct	7 ms	632 KB	Output is correct
62	Correct	9 ms	640 KB	Output is correct
63	Correct	8 ms	596 KB	Output is correct
64	Runtime error	104 ms	127456 KB	Execution killed with signal 11
65	Halted	0 ms	0 KB	-