Submission #1014941

#TimeUsernameProblemLanguageResultExecution timeMemory
1014941rainboyTiles (BOI24_tiles)C11
46 / 100
150 ms15300 KiB
#include <stdio.h> #include <string.h> #define N 200000 #define N_ (1 << 18) /* N_ = pow2(ceil(log2(N))) */ 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], n; int compare_y(int i, int j) { return yy[i] - yy[j]; } int compare_xy(int i, int j) { return xx[i] != xx[j] ? xx[i] - xx[j] : yy[i] - yy[j]; } 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; } } int yy1[N], n1; int sz[N_ * 2]; int ss1[N_ * 2], ss2[N_ * 2]; int ccp[N_ * 2], ssp[N_ * 2]; int ccq[N_ * 2], ssq[N_ * 2]; char good[N_ * 2]; char lz[N_]; int h_, n_; int flip(int c) { return c == 0 ? 0 : (c < 0 ? (c == -1 ? -2 : -1) : (c == 1 ? 2 : 1)); } void put(int i, int x) { int tmp; if (x == -1) { tmp = ss1[i], ss1[i] = ss2[i], ss2[i] = tmp; ccp[i] = flip(ccp[i]), ccq[i] = flip(ccq[i]); if (i < n_) lz[i] = flip(lz[i]); } else if (x != -2) { if (x == 0) ss1[i] = ss2[i] = 0; else if (x == 1) ss1[i] = sz[i], ss2[i] = 0; else ss1[i] = 0, ss2[i] = sz[i]; ccp[i] = ccq[i] = x, ssp[i] = ssq[i] = x == 0 ? 0 : sz[i]; good[i] = 1; if (i < n_) lz[i] = x; } } void pus(int i) { if (lz[i] != -2) put(i << 1 | 0, lz[i]), put(i << 1 | 1, lz[i]), lz[i] = -2; } void pul(int i) { if (lz[i] == -2) { int l = i << 1, r = l | 1; ss1[i] = ss1[l] + ss1[r], ss2[i] = ss2[l] + ss2[r]; ccp[i] = ccp[l]; if (ccp[l] == 0) ssp[i] = 0; else ssp[i] = ssp[l] < sz[l] || ccp[r] != ccp[l] ? ssp[l] : sz[l] + ssp[r]; ccq[i] = ccq[r]; if (ccq[r] == 0) ssq[i] = 0; else ssq[i] = ssq[r] < sz[r] || ccq[l] != ccq[r] ? ssq[r] : ssq[l] + sz[r]; good[i] = good[l] && good[r] && (ccq[l] != ccp[r] ? (ssq[l] == sz[l] || ssq[l] % 2 == 0) && (ssp[r] == sz[r] || ssp[r] % 2 == 0) : ssq[l] == sz[l] || ssp[r] == sz[r] || (ssq[l] + ssp[r]) % 2 == 0); } } void push(int i) { int h; for (h = h_; h > 0; h--) pus(i >> h); } void pull(int i) { while (i > 1) pul(i >>= 1); } void build() { int i; h_ = 0; while (1 << h_ < n1) h_++; n_ = 1 << h_; memset(lz, -2, n_ * sizeof *lz); memset(good, 1, n_ * 2 * sizeof *good); for (i = 0; i + 1 < n1; i++) sz[n_ + i] = yy1[i + 1] - yy1[i]; for (i = n_ - 1; i > 0; i--) sz[i] = sz[i << 1 | 0] + sz[i << 1 | 1], pul(i); } void update(int l, int r, int x) { int l_ = l += n_, r_ = r += n_; push(l_), push(r_); for ( ; l <= r; l >>= 1, r >>= 1) { if ((l & 1) == 1) put(l++, x); if ((r & 1) == 0) put(r--, x); } pull(l_), pull(r_); } int query(int l, int r) { int s, s1, s2; push(l += n_), push(r += n_); s = 0, s1 = s2 = 0; for ( ; l <= r; l >>= 1, r >>= 1) { if ((l & 1) == 1) s += sz[l], s1 += ss1[l], s2 += ss2[l], l++; if ((r & 1) == 0) s += sz[r], s1 += ss1[r], s2 += ss2[r], r--; } return s1 == 0 && s2 == 0 ? 1 : (s1 == s ? 0 : -1); } int main() { static int ii[N], xx_[N], yy_[N]; int i, j, x1, x2, y, y1, y2, ans, t; scanf("%d%*d", &n); for (i = 0; i < n; i++) scanf("%d%d", &xx[i], &yy[i]); n1 = 0; for (i = 0; i < n; i++) if ((xx[i] != xx[(i + 1) % n]) != (xx[i] != xx[(i - 1 + n) % n])) xx_[n1] = xx[i], yy_[n1] = yy[i], n1++; memcpy(xx, xx_, n1 * sizeof *xx_), memcpy(yy, yy_, n1 * sizeof *yy_), n = n1; for (i = 0; i < n; i++) ii[i] = i; compare = compare_y, sort(ii, 0, n); n1 = 0; for (i = 0; i < n; i = j) { j = i, y = yy[ii[i]]; while (j < n && yy[ii[j]] == y) yy[ii[j++]] = n1; yy1[n1++] = y; } build(n1); compare = compare_xy, sort(ii, 0, n); ans = 0; for (i = 0; i + 1 < n; i += 2) { y1 = yy[ii[i]], y2 = yy[ii[i + 1]]; t = query(y1, y2 - 1); if (t == -1) break; update(y1, y2 - 1, t); if (i + 2 < n && xx[ii[i + 2]] != xx[ii[i + 1]]) { if (!good[1] || ssp[1] % 2 != 0 || ssq[1] % 2 != 0) break; x1 = xx[ii[i + 1]], x2 = xx[ii[i + 2]]; if (ss2[1] == 0) ans = max(ans, x1 + (x2 - x1) / 2 * 2); if (ss1[1] == 0) ans = max(ans, x1 + 1 + (x2 - x1 - 1) / 2 * 2); if ((x2 - x1) % 2 != 0) put(1, -1); } } printf("%d\n", ans); return 0; }

Compilation message (stderr)

Main.c: In function 'main':
Main.c:166:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |  scanf("%d%*d", &n);
      |  ^~~~~~~~~~~~~~~~~~
Main.c:168:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  168 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...