Submission #817193

#TimeUsernameProblemLanguageResultExecution timeMemory
817193rainboyCell Automaton (JOI23_cell)C11
49 / 100
415 ms127456 KiB
#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 (stderr)

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);
      |    ^~~~~~~~~~~~~~~
#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...