제출 #1125402

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1125402		sleepntsheep	Road Construction (JOI21_road_construction)	C11	100 / 100	4655 ms	47304 KiB

road_construction

/*
 * sol: transform input (x, y) to (x + y, x - y)
 *    now, manhattan distance is transformed to Chebyshev distance
 *    since counting points closer to i than certain distance is now
 *    just rectangular sum query
 *
 *    we can find k-th integer of the output by binary searching on distance
 *
 *    and counting edges under certain distance by persistent segment tree (2drq)
 *            (the persistent segment tree can be replaced with offline normal segment tree
 *            , for lower constant)
 *    
 *    after obtaining k-th smallest edge, iterate all edge smaller than that edge
 *    by constructing merge-sort tree where indices are compressed x-coordinate
 *    and each node in the merge-sort tree is sorted by y-coordinate
 *    
 *    with the merge-sort tree, can iterate all edge less than (distance of k-th smallest edge)
 *    efficiently
 *
 *    time complexity: O(lg(4e9)nlgn + n*lgn+k*lgn)
 */

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,tune=native")
#include <stdio.h>
#include <stdlib.h>

#define N (1 << 18)
#define M (1 << 24)

int n, k,
    ii[N],  /* indices sorted by x */
    ii2[N],  /* indices sorted by y */
    rt[1 + N];

int x3[N], y3[N]; /* x2[x3[i]] = x[i] */
long long x[N], y[N]; /* inputs, transformed to (x+y, x-y) */
int x2[N], y2[N];  /* sorted x[] and y[] */
unsigned ee[N * 2], last; /* answers */
int eo;

int *tt[N * 2], to[N * 2]; /* merge sort tree */

int st[N * 2];

int pool[M], alloc; /* for merge sort tree */

int *pool_alloc(int n);

long long max(long long a, long long b);
unsigned distance(int i, int j);

void input();
void prepare();
void answer();

int lower_bound(int *a, int n, long long x);
int prev_upper_bound(int *a, int n, long long x);
void add(int p, int k);
int sum(int x, int y);
void fetch_not_exceeding(unsigned dist);
void construct_merge_sort_tree();

unsigned kth(int k);
long long count(long long v);

int direction(long long x)
{
  return x > 0 ? 1 : (x ? -1 : 0);
}

int cci(const void *i, const void *j)
{
  return direction(*(int*)i * 1ll - *(int*)j);
}

int ccu(const void *i, const void *j)
{
  return direction((long long)(*(unsigned*)i) - (long long)(*(unsigned*)j));
}

int ccx(const void *i, const void *j)
{
  return direction((long long)x[*(int*)i] - (long long)x[*(int*)j]);
}

int ccy(const void *i, const void *j)
{
  return direction((long long)y[*(int*)i] - (long long)y[*(int*)j]);
}

int main()
{
  input();
  prepare();
  construct_merge_sort_tree();
  answer();
  return 0;
}

void input()
{
  int i, xx, yy;

  (void)scanf("%d%d", &n, &k);
  for (i = 0; i < n; ++i)
  {
    (void)scanf("%d%d", &xx, &yy);
    x[i] = xx + yy;
    y[i] = xx - yy;
    x2[i] = x[i];
    y2[i] = y[i];
  }
}

void prepare()
{
  int i;
  qsort(x2, n, sizeof *x2, cci);
  qsort(y2, n, sizeof *y2, cci);

  for (i = 0; i < n; ++i)
  {
    ii[i] = i;
    ii2[i] = i;
  }
  qsort(ii, n, sizeof *ii, ccx);
  qsort(ii2, n, sizeof *ii2, ccy);

  for (i = 0; i < n; ++i)
  {
    x3[i] = lower_bound(x2, n, x[i]);
    y3[i] = lower_bound(y2, n, y[i]);
  }
}

void answer()
{
  int i;

  last = kth(k);

  fprintf(stderr, "kth(%d) = %u\n", k, last);

  fetch_not_exceeding(last - 1);

  qsort(ee, eo, sizeof *ee, ccu);

  for (i = k - 1; i >= 0; --i)
    if (ee[i] == 0)
      ee[i] = last;
  for (i = 0; i < k; ++i)
    printf("%u\n", ee[i]);
}

int lower_bound(int *a, int n, long long x)
{
  int lower, upper, mid;
  lower = -1;
  upper = n;
  while (upper - lower > 1)
  {
    mid = lower + (upper - lower) / 2;
    if (a[mid] >= x)
      upper = mid;
    else
      lower = mid;
  }
  return upper;
}

int prev_upper_bound(int *a, int n, long long x)
{
  int lower, upper, mid;
  lower = -1;
  upper = n;
  while (upper - lower > 1)
  {
    mid = lower + (upper - lower) / 2;
    if (a[mid] <= x)
      lower = mid;
    else
      upper = mid;
  }
  return lower;
}

long long max(long long a, long long b)
{
  return a > b ? a : b;
}

unsigned distance(int i, int j)
{
  return max(llabs(x[i] - x[j]), llabs(y[i] - y[j]));
}

unsigned kth(int k)
{
  unsigned lower, upper, mid;
  lower = 0;
  upper = 4e9 + 1;
  while (upper - lower > 1)
  {
    mid = lower + (upper - lower) / 2;
    if (count(mid) >= k)
      upper = mid;
    else 
      lower = mid;
  }
  return upper;
}

void construct_merge_sort_tree()
{
  int i, j;
  for (i = 0; i < n; ++i)
    for (j = x3[ii2[i]] + n; j; j /= 2)
      ++to[j];

  for (i = 1; i < 2 * n; ++i)
  {
    tt[i] = pool_alloc(to[i]);
    to[i] = 0;
  }

  for (i = 0; i < n; ++i)
    for (j = x3[ii2[i]] + n; j; j /= 2)
      tt[j][to[j]++] = ii2[i];
}

void make_edge(int i, int j)
{
  if (i == j || eo >= k)
    return;
  ee[eo++] = distance(i, j);
}

int mode;

void fetch_in_node(int i, int v, long long dist)
{
  int j, lower, upper, mid;
  lower = -1, upper = to[v];
  while (upper - lower > 1)
  {
    mid = lower + (upper - lower) / 2;
    if (y[tt[v][mid]] >= (mode ? y[i] + 1: y[i] - dist))
      upper = mid;
    else
      lower = mid;
  }
  j = upper;
  while (eo < k && j < to[v] && y[tt[v][j]] <= y[i] + dist)
    make_edge(i, tt[v][j++]);
}

void fetch_(int i, int l, int r, long long dist)
{
  for (l += n, r += n + 1; l < r; l /= 2, r /= 2)
  {
    if (l & 1)
      fetch_in_node(i, l++, dist);
    if (r & 1)
      fetch_in_node(i, --r, dist);
  }
}

void fetch_not_exceeding(unsigned dist)
{
  int w, i;

  for (i = 0; eo < k && i < n; ++i)
  {
    w = prev_upper_bound(x2, n, dist + x[i]);
    mode = 0;
    fetch_(i, x3[i] + 1, w, dist);
    mode = 1;
    fetch_(i, x3[i], x3[i], dist);
  }
}

void add(int p, int k)
{
  for (st[p += n] += k; p /= 2;)
    st[p] += k;
}

int sum(int x, int y)
{
  int z;
  z = 0;
  for (x += n, y += 1 + n; x < y; x /= 2, y /= 2)
  {
    if (x & 1)
      z += st[x++];
    if (y & 1)
      z += st[--y];
  }
  return z;
}

long long count(long long v)
{
  long long z;
  int i, p_left, p_right, jj0;
  static int y_1[N], y_2[N], *tag[N], sz[N];

  jj0 = alloc;

  for (i = 0; i < 2 * n; ++i)
    st[i] = 0;

  for (i = 0; i <= n; ++i)
    sz[i] = 0;

  z = 0;

  p_left = 0;
  p_right = 0;

  for (i = 0; i < n; ++i)
  {
    while (p_right < n && x[ii[p_right]] <= v + x[ii[i]])
      ++p_right;
    while (p_left < i && x[ii[p_left]] + v < x[ii[i]])
      ++p_left;

    y_1[i] = lower_bound(y2, n, y[ii[i]] - v);
    y_2[i] = prev_upper_bound(y2, n, y[ii[i]] + v);
    ++sz[p_right];
    ++sz[p_left];
  }

  for (i = 0; i <= n; ++i)
  {
    tag[i] = pool_alloc(sz[i]);
    sz[i] = 0;
  }

  p_left = 0;
  p_right = 0;
  for (i = 0; i < n; ++i)
  {
    while (p_right < n && x[ii[p_right]] <= v + x[ii[i]])
      ++p_right;
    while (p_left < i && x[ii[p_left]] + v < x[ii[i]])
      ++p_left;

    tag[p_left][sz[p_left]++]   = -i;
    tag[p_right][sz[p_right]++] =  i;
  }

  for (i = 1; i <= n; ++i)
  {
    int j, k;

    add(y3[ii[i - 1]], 1);

    for (k = 0; k < sz[i]; ++k)
    {
      j = tag[i][k];
      if (j < 0)
        z -= sum(y_1[-j], y_2[-j]);
      else
        z += sum(y_1[j] , y_2[j]);
    }
  }

  alloc = jj0;
  return (z - n) / 2;
}

int *pool_alloc(int n)
{
  int *u;
  u = pool + alloc;
  alloc += n;
  return u;
}

컴파일 시 표준 에러 (stderr) 메시지

road_construction.c: In function 'input':
road_construction.c:105:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |   (void)scanf("%d%d", &n, &k);
      |         ^~~~~~~~~~~~~~~~~~~~~
road_construction.c:108:11: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |     (void)scanf("%d%d", &xx, &yy);
      |           ^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 27 / 27
• Subtask 6: 35 / 35