Submission #666202

#TimeUsernameProblemLanguageResultExecution timeMemory
666202rainboyRoad Construction (JOI21_road_construction)C11
100 / 100
4447 ms19112 KiB
#include <stdio.h> #define N 250000 #define M 250000 #define INF 0x3f3f3f3f3f3f3f3fLL long long abs_(long long a) { return a > 0 ? a : -a; } 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 xx[N], yy[N]; int ii[N], n; long long dd[M]; int hh[M], m; long long *vv; 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 (vv[ii[j]] == vv[i_]) j++; else if (vv[ii[j]] < vv[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; } } int zz[N + 1], ll[N + 1], rr[N + 1], ii_[N + 1], _, u_, l_, r_; int node(int i) { zz[_] = rand_(); ll[_] = rr[_] = 0; ii_[_] = i; return _++; } void split(int u, int i) { int c; if (u == 0) { u_ = l_ = r_ = 0; return; } c = yy[ii_[u]] != yy[i] ? (yy[ii_[u]] < yy[i] ? -1 : 1) : ii_[u] - i; if (c < 0) { split(rr[u], i); rr[u] = l_, l_ = u; } else if (c > 0) { split(ll[u], i); ll[u] = r_, r_ = u; } else { u_ = u, l_ = ll[u], r_ = rr[u]; ll[u] = rr[u] = 0; } } int merge(int u, int v) { if (u == 0) return v; if (v == 0) return u; if (zz[u] < zz[v]) { rr[u] = merge(rr[u], v); return u; } else { ll[v] = merge(u, ll[v]); return v; } } void tr_add(int i) { split(u_, i); u_ = merge(merge(l_, node(i)), r_); } void tr_remove(int i) { split(u_, i); u_ = merge(l_, r_); } int tr_higher(long long y, int i) { int u = u_, i_ = -1; while (u) if (yy[ii_[u]] < y || yy[ii_[u]] == y && ii_[u] <= i) u = rr[u]; else i_ = ii_[u], u = ll[u]; return i_; } int count(int m, long long d) { int i, i_, j, j_, cnt; cnt = 0, _ = 1, u_ = 0; for (i = 0, j = 0; j < n; j++) { j_ = ii[j]; while (xx[j_] - xx[i_ = ii[i]] > d) tr_remove(i_), i++; i_ = tr_higher(yy[j_] - d, -1); while (i_ != -1 && yy[i_] - yy[j_] <= d) { dd[cnt++] = max(abs_(xx[i_] - xx[j_]), abs_(yy[i_] - yy[j_])); if (cnt == m) return m; i_ = tr_higher(yy[i_], i_); } tr_add(j_); } return cnt; } int main() { int cnt, h, i; long long lower, upper, d; scanf("%d%d", &n, &m); for (i = 0; i < n; i++) { int x, y; scanf("%d%d", &x, &y); xx[i] = x + y, yy[i] = x - y; } for (i = 0; i < n; i++) ii[i] = i; vv = xx, sort(ii, 0, n); lower = 0, upper = INF; while (upper - lower > 1) { d = (lower + upper) / 2; if (count(m, d) < m) lower = d; else upper = d; } d = upper; cnt = count(m, d - 1); while (cnt < m) dd[cnt++] = d; for (h = 0; h < m; h++) hh[h] = h; vv = dd, sort(hh, 0, m); for (h = 0; h < m; h++) printf("%lld\n", dd[hh[h]]); return 0; }

Compilation message (stderr)

road_construction.c: In function 'tr_higher':
road_construction.c:97:41: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   97 |   if (yy[ii_[u]] < y || yy[ii_[u]] == y && ii_[u] <= i)
      |                         ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
road_construction.c: In function 'main':
road_construction.c:128:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
road_construction.c:132:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |   scanf("%d%d", &x, &y);
      |   ^~~~~~~~~~~~~~~~~~~~~
#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...