Submission #819584

#TimeUsernameProblemLanguageResultExecution timeMemory
819584rainboyCell Automaton (JOI23_cell)C11
33 / 100
738 ms21588 KiB
#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 ((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]++; } } 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 < m1 && tt1[h1] < t) h1++; ans = (a * t * 2 + b) / 2; if (h1 < m1 && tt1[h1] == t) ans += cc1[h1]; } printf("%lld\n", ans); } } return 0; }

Compilation message (stderr)

cell.c: In function 'main':
cell.c:336:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  336 |  scanf("%d%d", &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~
cell.c:338:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  338 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cell.c:374:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  374 |    scanf("%lld", &t);
      |    ^~~~~~~~~~~~~~~~~
cell.c:393:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  393 |    scanf("%lld", &t);
      |    ^~~~~~~~~~~~~~~~~
cell.c:417:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  417 |    scanf("%lld", &t);
      |    ^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...