Submission #1125379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125379		sleepntsheep	Road Construction (JOI21_road_construction)	C11	7 / 100	8675 ms	94384 KiB

road_construction

#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)

#define assert_(x) if (!((x))) __builtin_trap()

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]; /* answers */
int eo;

int A[M], L[M], R[M], jj; /* persistent segment tree */

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

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);
int persist_new(int lc, int rc, int v);
int persist_add(int v, int l, int r, int p, int k);
int persist_sum(int v, int l, int r, 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()
{
  unsigned last;
  int i;

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

  fetch_not_exceeding(last - 1);
  fetch_not_exceeding(last);

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

  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;
}

int persist_new(int lc, int rc, int v)
{
  int i;
  i = ++jj;
  A[i] = A[lc] + A[rc] + v;
  L[i] = lc;
  R[i] = rc;
  return i;
}

int persist_add(int v, int l, int r, int p, int k)
{
  if (l == r)
    return persist_new(0, 0, A[v] + k);
  if (p <= (l + r) / 2)
    return persist_new(persist_add(L[v], l, (l + r) / 2, p, k), R[v], 0);
  return persist_new(L[v], persist_add(R[v], (l + r) / 2 + 1, r, p, k), 0);
}

int persist_sum(int v, int l, int r, int x, int y)
{
  if (r < x || y < l)
    return 0;
  if (x <= l && r <= y)
    return A[v];
  return persist_sum(L[v], l, (l + r) / 2, x, y)
      + persist_sum(R[v], (l + r) / 2 + 1, r, x, y);
}

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 prepare_count()
{
  static int f = 0;

  if (!f)
    ++f;
  else
    return;

  int i;
  if (!rt[1])
  {
    jj = 0;
    rt[0] = 0;
    for (i = 0; i < n; ++i)
      rt[i + 1] = persist_add(rt[i], 0, n, y3[ii[i]], 1);
  }
}

long long count(long long v)
{
  long long z;
  int i, p_left, p_right, y_1, y_2;

  prepare_count();

  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 = lower_bound(y2, n, y[ii[i]] - v);
    y_2 = prev_upper_bound(y2, n, y[ii[i]] + v);

    z += persist_sum(rt[p_right], 0, n, y_1, y_2) - persist_sum(rt[p_left], 0, n, y_1, y_2);
  }

  return (z - n) / 2;
}

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

Compilation message (stderr)

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

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