Submission #671353

#TimeUsernameProblemLanguageResultExecution timeMemory
671353rainboyHamburg Steak (JOI20_hamburg)C11
15 / 100
117 ms6596 KiB
#include <assert.h> #include <stdio.h> #include <stdlib.h> #define N 200000 #define LN 18 /* N_ = pow2(ceil(log2(N))) */ #define N_ (N * (LN + 1) + 1) #define K 4 #define INF 0x3f3f3f3f3f3f3f3fLL long long min(long long a, long long b) { return a < b ? a : b; } long long max(long long a, long long b) { return a > b ? a : b; } unsigned int X = 12345; int rand_() { return (X *= 3) >> 1; } long long xxl[N], xxr[N], yyl[N], yyr[N], xx[K], yy[K]; int n, k; long long *zz; 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) if (zz[ii[j]] == zz[i_]) j++; else if (zz[ii[j]] < zz[i_]) { 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 *xl1, *xr1, *yl1, *yr1; int ll_[N_], rr_[N_]; long long xxl_[N_], xxr_[N_], yyl_[N_], yyr_[N_]; int update(int t, int l, int r, int i, int i_) { static int _ = 1; int t_ = _++; ll_[t_] = ll_[t], rr_[t_] = rr_[t], xxl_[t_] = min(xxl_[t], xxr[i_]), xxr_[t_] = max(xxr_[t], xxl[i_]), yyl_[t_] = min(yyl_[t], yyr[i_]), yyr_[t_] = max(yyr_[t], yyl[i_]); if (r - l > 1) { int m = (l + r) / 2; if (i < m) ll_[t_] = update(ll_[t_], l, m, i, i_); else rr_[t_] = update(rr_[t_], m, r, i, i_); } return t_; } void query(int t, int l, int r, int ql, int qr) { int m; if (qr <= l || r <= ql || t == 0) return; if (ql <= l && r <= qr) { *xl1 = min(*xl1, xxl_[t]), *xr1 = max(*xr1, xxr_[t]), *yl1 = min(*yl1, yyl_[t]), *yr1 = max(*yr1, yyr_[t]); return; } m = (l + r) / 2; query(ll_[t], l, m, ql, qr), query(rr_[t], m, r, ql, qr); } int pierced(int i, int h_) { int h; for (h = 0; h < h_; h++) if (xxl[i] <= xx[h] && xx[h] <= xxr[i] && yyl[i] <= yy[h] && yy[h] <= yyr[i]) return 1; return 0; } void solve(int h_) { int h, i; long long xl, xr, yl, yr; xl = INF, xr = -1, yl = INF, yr = -1; for (i = 0; i < n; i++) if (!pierced(i, h_)) xl = min(xl, xxr[i]), xr = max(xr, xxl[i]), yl = min(yl, yyr[i]), yr = max(yr, yyl[i]); if (xl == INF) { for (h = h_; h < k; h++) xx[h] = 1, yy[h] = 1; for (h = 0; h < k; h++) printf("%lld %lld\n", xx[h], yy[h]); exit(0); } else if (k - h_ == 1) { xx[h_] = xl, yy[h_] = yl, solve(h_ + 1); } else if (k - h_ == 2) { xx[h_] = xl, yy[h_] = yl, solve(h_ + 1); xx[h_] = xl, yy[h_] = yr, solve(h_ + 1); } else if (k - h_ >= 3) { xx[h_] = xl, yy[h_] = yl, solve(h_ + 1); xx[h_] = xl, yy[h_] = yr, solve(h_ + 1); xx[h_] = xr, yy[h_] = yl, solve(h_ + 1); xx[h_] = xr, yy[h_] = yr, solve(h_ + 1); } } long long ll[N], rr[N], rr2[3][N]; int rr1[N]; int ii[3][N], nn[3], nn_[3], tt[3][N + 1]; long long xl, xr, yl, yr, z1, z2, z3, z4; void query_(int g, long long l, long long r) { int lower, upper, l_, r_; lower = -1, upper = nn[g]; while (upper - lower > 1) { int i = (lower + upper) / 2; if (ll[ii[g][i]] >= l) upper = i; else lower = i; } l_ = upper; lower = -1, upper = nn_[g]; while (upper - lower > 1) { int i = (lower + upper) / 2; if (rr2[g][i] <= r) lower = i; else upper = i; } r_ = upper; query(tt[g][l_], 0, nn_[g], 0, r_); } void query1(long long *xx, int n, int g) { static int ii_[K + 2]; int i; for (i = 0; i < n; i++) ii_[i] = i; zz = xx, sort(ii_, 0, n); for (i = 0; i + 1 < n; i++) query_(g, xx[ii_[i]] + 1, xx[ii_[i + 1]] - 1); } long long idx(long long x, long long y) { if (y == yl) return x - xl; if (x == xr) return z1 + y - yl; if (y == yr) return z2 + xr - x; if (x == xl) return z3 + yr - y; return -1; } void get_bounds(int h_) { static long long xx_[K + 2]; int h; long long x_; if (h_ == 0) { *xl1 = xl, *xr1 = xr, *yl1 = yl, *yr1 = yr; return; } *xl1 = INF, *xr1 = -1, *yl1 = INF, *yr1 = -1; xx_[0] = -1; x_ = z4; for (h = 0; h < h_; h++) x_ = min(x_, xx_[h + 1] = idx(xx[h], yy[h])); xx_[h_ + 1] = x_ + z4; query1(xx_, h_ + 2, 0); xx_[0] = -1; for (h = 0; h < h_; h++) xx_[h + 1] = xx[h]; xx_[h_ + 1] = INF; query1(xx_, h_ + 2, 1); xx_[0] = -1; for (h = 0; h < h_; h++) xx_[h + 1] = yy[h]; xx_[h_ + 1] = INF; query1(xx_, h_ + 2, 2); } void solve_(int h_) { int h, i; long long xl_, yl_, xr_, yr_; if (h_ > 0 && idx(xx[h_ - 1], yy[h_ - 1]) == -1) return; xl1 = &xl_, xr1 = &xr_, yl1 = &yl_, yr1 = &yr_, get_bounds(h_); if (xl_ == INF) { for (h = h_; h < k; h++) xx[h] = 1, yy[h] = 1; for (h = 0; h < k; h++) printf("%lld %lld\n", xx[h], yy[h]); exit(0); } else if (k - h_ == 1) { xx[h_] = xl_, yy[h_] = yl_, solve_(h_ + 1); } else if (k - h_ == 2) { xx[h_] = xl_, yy[h_] = yl_, solve_(h_ + 1); xx[h_] = xl_, yy[h_] = yr_, solve_(h_ + 1); xx[h_] = xr_, yy[h_] = yl_, solve_(h_ + 1); xx[h_] = xr_, yy[h_] = yr_, solve_(h_ + 1); } else if (k - h_ == 3) { xx[h_] = xl_, yy[h_] = yl_, solve_(h_ + 1); xx[h_] = xl_, yy[h_] = yr_, solve_(h_ + 1); xx[h_] = xr_, yy[h_] = yl_, solve_(h_ + 1); xx[h_] = xr_, yy[h_] = yr_, solve_(h_ + 1); } else { xx[h_] = xl_; for (i = 0; i < n; i++) yy[h_] = yyl[i], solve_(h_ + 1); } } int main() { int g, i, i_; long long l, r; scanf("%d%d", &n, &k); for (i = 0; i < n; i++) scanf("%lld%lld%lld%lld", &xxl[i], &yyl[i], &xxr[i], &yyr[i]); solve(0); xl = INF, xr = -1, yl = INF, yr = -1; for (i = 0; i < n; i++) xl = min(xl, xxr[i]), xr = max(xr, xxl[i]), yl = min(yl, yyr[i]), yr = max(yr, yyl[i]); assert(k == 4 && xl < xr && yl < yr); z1 = xr - xl, z2 = z1 + yr - yl, z3 = z2 + xr - xl, z4 = z3 + yr - yl; for (i = 0; i < n; i++) xxl[i] = max(xxl[i], xl), xxr[i] = min(xxr[i], xr), yyl[i] = max(yyl[i], yl), yyr[i] = min(yyr[i], yr); for (i = 0; i < n; i++) if (xl < xxl[i] && xxr[i] < xr && yyl[i] == yl && yyr[i] == yr) ll[i] = xxl[i], rr[i] = xxr[i], ii[1][nn[1]++] = i; else if (yl < yyl[i] && yyr[i] < yr && xxl[i] == xl && xxr[i] == xr) ll[i] = yyl[i], rr[i] = yyr[i], ii[2][nn[2]++] = i; else { l = INF, r = -1; if (yyl[i] == yl) l = min(l, xxl[i] - xl), r = max(r, xxr[i] - xl); if (xxr[i] == xr) l = min(l, z1 + yyl[i] - yl), r = max(r, z1 + yyr[i] - yl); if (xxl[i] == xl && yyl[i] == yl) l += z4, r += z4; if (yyr[i] == yr) l = min(l, z2 + xr - xxr[i]), r = max(r, z2 + xr - xxl[i]); if (xxl[i] == xl) l = min(l, z3 + yr - yyr[i]), r = max(r, z3 + yr - yyl[i]); if (l >= z4) l -= z4, r -= z4; ll[i] = l, rr[i] = r, ii[0][nn[0]++] = i; } xxl_[0] = INF, xxr_[0] = -1, yyl_[0] = INF, yyr_[0] = -1; for (g = 0; g < 3; g++) { zz = rr, sort(ii[g], 0, nn[g]); for (i = 0; i < nn[g]; i++) { i_ = ii[g][i]; rr1[i_] = nn_[g]; if (i + 1 == nn[g] || rr[ii[g][i + 1]] != rr[i_]) rr2[g][nn_[g]++] = rr[i_]; } zz = ll, sort(ii[g], 0, nn[g]); for (i = nn[g] - 1; i >= 0; i--) { i_ = ii[g][i]; tt[g][i] = update(tt[g][i + 1], 0, nn_[g], rr1[i_], i_); } } solve_(0); return 0; }

Compilation message (stderr)

hamburg.c: In function 'main':
hamburg.c:228:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  228 |  scanf("%d%d", &n, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~
hamburg.c:230:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  230 |   scanf("%lld%lld%lld%lld", &xxl[i], &yyl[i], &xxr[i], &yyr[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...
#Verdict Execution timeMemoryGrader output
Fetching results...