Submission #926839

#TimeUsernameProblemLanguageResultExecution timeMemory
926839rainboyCell Automaton (JOI23_cell)C11
0 / 100
8093 ms76964 KiB
#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 long long abs_(long long a) { return a > 0 ? a : -a; } int min(int a, int b) { return a < b ? a : b; } long long max(long long a, long long b) { return a > b ? a : b; } unsigned int Z = 12345; int rand_() { return (Z *= 3) >> 1; } int xx[N], yy[N], n; int tt[Q]; long long ans[Q]; int q; int compare_x(int i, int j) { return xx[i] - xx[j]; } int tt_[N]; int compare_t_(int i, int j) { return tt_[i] != tt_[j] ? (tt_[i] < tt_[j] ? -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; } } 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; long long b, t; 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; 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 += (long long) tt_[i_] * 2; i++; } ans[h] = 0; while (i < n - 1 && tt_[i_ = ii[i]] == t) { ans[h] += t - 1; a -= 4, b += (long long) tt_[i_] * 2; i++; } ans[h] += (long long) a * t + b; } } long long uu[N], vv[N]; 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 jj[N]; int cnt, h, i, j, r, 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 (r = 0; r < 4; r++) { for (i = 0; i < n; i++) { cnt = 0; for (j = 0; j < n; j++) if (j != i) { if (vv[i] > vv[j] || vv[i] == vv[j] && i < j) continue; tt_[j] = (max(abs_(uu[i] - uu[j]), abs_(vv[i] - vv[j])) + (i < j ? 2 : 1)) / 2; jj[cnt++] = j; } compare = compare_t_, sort(jj, 0, cnt); add(0, 1, 0); u = uu[i], ul = -INF, ur = INF, t = INF; for (h = 0; h <= cnt; h++) { if (h == cnt) { t = ul != -INF && ur != INF ? (ur - ul) / 2 + 1 : INF; break; } j = jj[h], t = tt_[j]; 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) ul = u_, add(t, -1, (u - u_) / 2); 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) ur = u_, add(t, -1, (u_ - u + 2) / 2); 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_() % 2001 - 1000, yy[i] = rand_() % 2001 - 1000; 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 1 stress(); #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 (stderr)

cell.c: In function 'solve6':
cell.c:153:42: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  153 |      if (vv[i] > vv[j] || vv[i] == vv[j] && i < j)
      |                           ~~~~~~~~~~~~~~~^~~~~~~~
cell.c: In function 'main':
cell.c:236:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  236 |  scanf("%d%d", &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~
cell.c:238:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  238 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cell.c:240:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  240 |   scanf("%d", &tt[h]);
      |   ^~~~~~~~~~~~~~~~~~~
#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...