oj.uz

Submission #927312

# Submission time Handle Problem Language Result Execution time Memory
927312 2024-02-14T17:42:39 Z rainboy Cell Automaton (JOI23_cell) C
58 / 100
 258 ms 72288 KB 
#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

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

unsigned int Z = 12345;

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

int xx[N], yy[N], uu[N], vv[N]; int tt_[N], n;
int tt[Q]; long long ans[Q]; int q;

int *ww;

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 = ww[ii[j]] != ww[i_] ? (ww[ii[j]] < ww[i_] ? -1 : 1) : (xx[ii[j]] != xx[i_] ? (xx[ii[j]] < xx[i_] ? -1 : 1) : 0);

			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, t;
	long long b;

	for (i = 0; i < n; i++)
		ii[i] = i;
	ww = xx, sort(ii, 0, n);
	for (i = 0; i + 1 < n; i++) {
		tt_[i] = xx[ii[i + 1]] - xx[ii[i]];
		ii[i] = i;
	}
	ww = tt_, 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 += tt_[i_] * 2;
			i++;
		}
		ans[h] = 0;
		while (i < n - 1 && tt_[i_ = ii[i]] == t) {
			ans[h] += t - 1;
			a -= 4, b += tt_[i_] * 2;
			i++;
		}
		ans[h] += (long long) a * t + b;
	}
}

int xx_[N], yy_[N];

void compress(int *xx, int *xx_, int n) {
	static int ii[N];
	int i, x;

	for (i = 0; i < n; i++)
		ii[i] = i;
	ww = xx, sort(ii, 0, n);
	for (i = 0, x = 0; i < n; i++)
		xx_[ii[i]] = i + 1 == n || xx[ii[i + 1]] != xx[ii[i]] ? x++ : x;
}

int *ej[N], eo[N];

void append(int i, int j) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
	ej[i][o] = j;
}

int ft[N];

int min_(int i, int j) {
	return j == -1 || i != -1 && (vv[i] < vv[j] || vv[i] == vv[j] && i < j) ? i : j;
}

void update(int i, int n, int x) {
	while (i < n) {
		ft[i] = min_(ft[i], x);
		i |= i + 1;
	}
}

int query(int i) {
	int x = -1;

	while (i >= 0) {
		x = min_(x, ft[i]);
		i &= i + 1, i--;
	}
	return x;
}

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 ii[N], qu[N], jjl[N * 4], jjr[N * 4];
	int cnt, h, i, i_, j, j_, jl, jr, r, o, t, 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 (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]), eo[i] = 0;
	compress(xx, xx_, n), compress(yy, yy_, n);
	for (r = 0; r < 4; r++) {
		for (i = 0; i < n; i++)
			ii[i] = i;
		ww = uu, sort(ii, 0, n);
		memset(ft, -1, n * sizeof *ft);
		for (i = 0; i < n; i = j) {
			j = i + 1;
			while (j < n && uu[ii[j]] == uu[ii[i]])
				j++;
			for (h = i; h < j; h++) {
				i_ = ii[h], j_ = query(n - 1 - xx_[i_]);
				if (j_ != -1)
					append(i_, j_), append(j_, i_);
				update(n - 1 - xx_[i_], n, i_);
			}
			cnt = 0;
			for (h = i; h < j; h++) {
				i_ = ii[h];
				while (cnt && qu[cnt - 1] > i_)
					cnt--;
				if (cnt) {
					j_ = qu[cnt - 1];
					append(i_, j_), append(j_, i_);
				}
				qu[cnt++] = i_;
			}
		}
		memset(ft, -1, n * sizeof *ft);
		for (j = n; j > 0; j = i) {
			i = j - 1;
			while (i > 0 && uu[ii[i - 1]] == uu[ii[j - 1]])
				i--;
			for (h = i; h < j; h++) {
				i_ = ii[h], j_ = query(n - 1 - yy_[i_]);
				if (j_ != -1)
					append(i_, j_), append(j_, i_);
				update(n - 1 - yy_[i_], n, i_);
			}
		}
		for (i = 0; i < n; i++) {
			tmp = xx[i], xx[i] = -yy[i], yy[i] = tmp;
			tmp = xx_[i], xx_[i] = n - 1 - yy_[i], yy_[i] = tmp;
			tmp = uu[i], uu[i] = -vv[i], vv[i] = tmp;
		}
	}
	for (i = 0; i < n; i++) {
		for (o = 0; o < eo[i]; o++) {
			j = ej[i][o];
			tt_[j] = ((long long) abs_(xx[j] - xx[i]) + abs_(yy[j] - yy[i]) + (i < j ? 2 : 1)) / 2;
		}
		ww = tt_, sort(ej[i], 0, eo[i]);
	}
	cnt = 0;
	for (r = 0; r < 4; r++) {
		for (i = 0; i < n; i++) {
			u = uu[i], ul = -INF, jl = -1, ur = INF, jr = -1, t_ = -1;
			for (o = 0; o < eo[i]; o++) {
				j = ej[i][o], t = ((long long) abs_(xx[j] - xx[i]) + abs_(yy[j] - yy[i]) + (i < j ? 2 : 1)) / 2;
				if (vv[j] < vv[i] || vv[j] == vv[i] && j > i)
					continue;
				if (ul != -INF && ur != INF && ul + t > ur - t + 1 && t != t_)
					break;
				t_ = t;
				if (uu[j] < u) {
					u_ = uu[j] + (i < j ? 0 : 1);
					if (ul == -INF)
						ul = u_, jl = j;
					else {
						ul = max(ul, u_);
						if (uu[jl] < uu[j] || uu[jl] == uu[j] && jl > j)
							jl = j;
					}
				} else {
					u_ = uu[j] - (i < j ? 0 : 1);
					if (ur == INF)
						ur = u_, jr = j;
					else {
						ur = min(ur, u_);
						if (uu[jr] > uu[j] || uu[jr] == uu[j] && jr > j)
							jr = j;
					}
				}
			}
			if (jl != -1 && jr != -1)
				jjl[cnt] = jl, jjr[cnt] = jr, cnt++;
		}
		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 = 0; h < cnt; h++) {
		jl = jjl[h], jr = jjr[h];
		append(jl, jr), append(jr, jl);
	}
	for (i = 0; i < n; i++) {
		for (o = 0; o < eo[i]; o++) {
			j = ej[i][o];
			tt_[j] = ((long long) abs_(xx[j] - xx[i]) + abs_(yy[j] - yy[i]) + (i < j ? 2 : 1)) / 2;
		}
		ww = tt_, sort(ej[i], 0, eo[i]);
	}
	for (r = 0; r < 4; r++) {
		for (i = 0; i < n; i++) {
			add(0, 1, 0);
			u = uu[i], ul = -INF, ur = INF, t = INF;
			for (o = 0; o <= eo[i]; o++) {
				if (o == eo[i]) {
					t = ul != -INF && ur != INF ? (ur - ul) / 2 + 1 : INF;
					break;
				}
				j = ej[i][o], t = ((long long) abs_(xx[j] - xx[i]) + abs_(yy[j] - yy[i]) + (i < j ? 2 : 1)) / 2;
				if (vv[j] < vv[i] || vv[j] == vv[i] && j > i)
					continue;
				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)
						add(t, -1, (u - u_) / 2), ul = u_;
					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)
						add(t, -1, (u_ - u + 2) / 2), ur = u_;
					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_() % 21 - 10, yy[i] = rand_() % 21 - 10;
		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();
	return 0;
#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

cell.c: In function 'append':
cell.c:131:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
  131 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
cell.c: In function 'min_':
cell.c:139:64: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  139 |  return j == -1 || i != -1 && (vv[i] < vv[j] || vv[i] == vv[j] && i < j) ? i : j;
      |                                                 ~~~~~~~~~~~~~~~^~~~~~~~
cell.c:139:28: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  139 |  return j == -1 || i != -1 && (vv[i] < vv[j] || vv[i] == vv[j] && i < j) ? i : j;
      |                    ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cell.c: In function 'solve6':
cell.c:244:41: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  244 |     if (vv[j] < vv[i] || vv[j] == vv[i] && j > i)
      |                          ~~~~~~~~~~~~~~~^~~~~~~~
cell.c:255:45: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  255 |       if (uu[jl] < uu[j] || uu[jl] == uu[j] && jl > j)
      |                             ~~~~~~~~~~~~~~~~^~~~~~~~~
cell.c:264:45: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  264 |       if (uu[jr] > uu[j] || uu[jr] == uu[j] && jr > j)
      |                             ~~~~~~~~~~~~~~~~^~~~~~~~~
cell.c:298:41: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  298 |     if (vv[j] < vv[i] || vv[j] == vv[i] && j > i)
      |                          ~~~~~~~~~~~~~~~^~~~~~~~
cell.c: In function 'main':
cell.c:369:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  369 |  scanf("%d%d", &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~
cell.c:371:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  371 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cell.c:373:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  373 |   scanf("%d", &tt[h]);
      |   ^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 20824 KB Output is correct
2 Correct 3 ms 20828 KB Output is correct
3 Correct 3 ms 20828 KB Output is correct
4 Correct 3 ms 20828 KB Output is correct
5 Correct 3 ms 20828 KB Output is correct
6 Correct 3 ms 20824 KB Output is correct
7 Correct 3 ms 20828 KB Output is correct
8 Correct 258 ms 72288 KB Output is correct
9 Correct 2 ms 20828 KB Output is correct
10 Correct 2 ms 20828 KB Output is correct
11 Correct 2 ms 20828 KB Output is correct
12 Correct 7 ms 21084 KB Output is correct
13 Correct 7 ms 21168 KB Output is correct
14 Incorrect 7 ms 21084 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 20824 KB Output is correct
2 Correct 3 ms 20828 KB Output is correct
3 Correct 3 ms 20828 KB Output is correct
4 Correct 3 ms 20828 KB Output is correct
5 Correct 3 ms 20828 KB Output is correct
6 Correct 3 ms 20824 KB Output is correct
7 Correct 3 ms 20828 KB Output is correct
8 Correct 258 ms 72288 KB Output is correct
9 Correct 2 ms 20828 KB Output is correct
10 Correct 2 ms 20828 KB Output is correct
11 Correct 2 ms 20828 KB Output is correct
12 Correct 7 ms 21084 KB Output is correct
13 Correct 7 ms 21168 KB Output is correct
14 Incorrect 7 ms 21084 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 13984 KB Output is correct
2 Correct 42 ms 14676 KB Output is correct
3 Correct 42 ms 14684 KB Output is correct
4 Correct 43 ms 14684 KB Output is correct
5 Correct 43 ms 14732 KB Output is correct
6 Correct 46 ms 14672 KB Output is correct
7 Correct 41 ms 14748 KB Output is correct
8 Correct 2 ms 18776 KB Output is correct
9 Correct 3 ms 18780 KB Output is correct
10 Correct 4 ms 20828 KB Output is correct
11 Correct 46 ms 14748 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 13984 KB Output is correct
2 Correct 42 ms 14676 KB Output is correct
3 Correct 42 ms 14684 KB Output is correct
4 Correct 43 ms 14684 KB Output is correct
5 Correct 43 ms 14732 KB Output is correct
6 Correct 46 ms 14672 KB Output is correct
7 Correct 41 ms 14748 KB Output is correct
8 Correct 2 ms 18776 KB Output is correct
9 Correct 3 ms 18780 KB Output is correct
10 Correct 4 ms 20828 KB Output is correct
11 Correct 46 ms 14748 KB Output is correct
12 Correct 117 ms 26632 KB Output is correct
13 Correct 116 ms 26640 KB Output is correct
14 Correct 115 ms 26708 KB Output is correct
15 Correct 122 ms 26708 KB Output is correct
16 Correct 71 ms 31100 KB Output is correct
17 Correct 72 ms 31060 KB Output is correct
18 Correct 81 ms 36268 KB Output is correct
19 Correct 118 ms 27160 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 21080 KB Output is correct
2 Correct 7 ms 21084 KB Output is correct
3 Correct 12 ms 21164 KB Output is correct
4 Correct 10 ms 21336 KB Output is correct

Subtask #6
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 21080 KB Output is correct
2 Correct 7 ms 21084 KB Output is correct
3 Correct 12 ms 21164 KB Output is correct
4 Correct 10 ms 21336 KB Output is correct
5 Correct 84 ms 35860 KB Output is correct
6 Correct 85 ms 35732 KB Output is correct
7 Correct 87 ms 35864 KB Output is correct
8 Correct 87 ms 35916 KB Output is correct
9 Correct 87 ms 35872 KB Output is correct
10 Correct 87 ms 35860 KB Output is correct
11 Correct 91 ms 37032 KB Output is correct
12 Correct 95 ms 37124 KB Output is correct

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 20824 KB Output is correct
2 Correct 3 ms 20828 KB Output is correct
3 Correct 3 ms 20828 KB Output is correct
4 Correct 3 ms 20828 KB Output is correct
5 Correct 3 ms 20828 KB Output is correct
6 Correct 3 ms 20824 KB Output is correct
7 Correct 3 ms 20828 KB Output is correct
8 Correct 258 ms 72288 KB Output is correct
9 Correct 2 ms 20828 KB Output is correct
10 Correct 2 ms 20828 KB Output is correct
11 Correct 2 ms 20828 KB Output is correct
12 Correct 7 ms 21084 KB Output is correct
13 Correct 7 ms 21168 KB Output is correct
14 Incorrect 7 ms 21084 KB Output isn't correct
15 Halted 0 ms 0 KB -