Submission #1125291

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125291		sleepntsheep	Road Construction (JOI21_road_construction)	C11	0 / 100	5074 ms	85792 KiB

road_construction

#include <stdio.h>

#define N 250000
#define M (250000 * 30)

int n, k,
    x[N], y[N], /* inputs */
    x2[N], y2[N], /* x[] and y[] seperatedly sorted */
    x3[N], y3[N], /* x2[x3[i]] = x[i] */
    ii[N],  /* indices sorted by x */
    ii2[N],  /* indices sorted by y */
    rt[N], L[M], R[M], jj,
    ee[N * 2], eo;

long long A[M]; /* persistent segment tree */

void csort(int *a, int n, int offset)
{
#define B 45000
  int i;
  static int count[B],
              pass_1[N];

  for (i = 0; i < B; ++i)
    count[i] = 0;

  for (i = 0; i < n; ++i)
  {
    a[i] += offset;
    ++count[a[i] % B];
  }

  for (i = B - 2; i >= 0; --i)
    count[i] += count[i + 1];

  for (i = 0; i < n; ++i)
    pass_1[--count[a[i] % B]] = a[i];

  for (i = 0; i < B; ++i)
    count[i] = 0;

  for (i = 0; i < n; ++i)
    ++count[pass_1[i] / B];

  for (i = 1; i < B; ++i)
    count[i] += count[i - 1];

  for (i = 0; i < n; ++i)
    a[--count[pass_1[i] / B]] = pass_1[i] - offset;
#undef B
}

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

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

int persist_new0(int val)
{
  int i;
  i = ++jj;
  A[i] = val;
  L[i] = R[i] = 0;
  return i;
}

int persist_new1(int lc, int rc)
{
  int i;
  i = ++jj;
  A[i] = A[lc] + A[rc];
  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_new0(A[v] + k);
  if (p <= (l + r) / 2)
    return persist_new1(persist_add(L[v], l, (l + r) / 2, p, k), R[v]);
  return persist_new1(L[v], persist_add(R[v], (l + r) / 2 + 1, r, p, k));
}

long long 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 count(long long v)
{
  long long z;
  int i, p_left, p_right;

  jj = 0;
  rt[0] = 0;

  for (i = 0; i < n; ++i)
    rt[i + 1] = persist_add(rt[i], 0, n, y3[ii[i]], 1);

  z = 0;

  p_left = 0;
  p_right = 0;
  for (i = 0; i < n; ++i)
  {
    int y_1, y_2;
    while (p_right + 1 < n && x[ii[p_right + 1]] <= 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;
    z += persist_sum(rt[p_right + 1], 0, n, y_1, y_2) - persist_sum(rt[p_left], 0, n, y_1, y_2);
  }

  return z / 2;
}

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

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

void prepare()
{
  static int freq[N], ptr[N];
  int i, run;

  csort(x2, n, 1e9);
  csort(y2, n, 1e9);

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

  run = 0;
  for (i = 0; i < n; ++i)
  {
    ptr[i] = run;
    run += freq[i];
  }

  for (i = 0; i < n; ++i)
    ii[ptr[x3[i]]++] = i;

  for (i = 0; i < n; ++i)
  {
    ptr[i] = 0;
    freq[i] = 0;
  }

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

  run = 0;
  for (i = 0; i < n; ++i)
  {
    ptr[i] = run;
    run += freq[i];
  }
}

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

  return upper;
}

long long abs_(long long x)
{
  return x < 0 ? -x : x;
}

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

long long distance(int i, int j)
{
  return max(abs_(x[i] * 1ll - x[j]), abs_(y[i] * 1ll - y[j]));
}

void make_edge(int i, int j, long long threshold)
{
  long long dd = distance(i, j);

  if (eo >= k)
    return;
  if (persist_sum(rt[i], 0, n, j, j))
    return;
  if (dd > threshold)
    return;

  rt[i] = persist_add(rt[i], 0, n, j, 1);
  ee[eo++] = distance(i, j);
  if (ee[eo - 1] > 2e9)
    __builtin_trap();
}

void fetch_not_exceeding(long long d)
{
  int i, j, k;

  j = 0;
  for (i = 0; i < n; ++i)
  {
    while (j < n && x[ii[j]] <= x[ii[i]] + d)
      ++j;

    for (k = i + 1; k < j; ++k)
      make_edge(i, k, d);
  }
  j = 0;
  for (i = 0; i < n; ++i)
  {
    while (j < n && y[ii[j]] <= y[ii[i]] + d)
      ++j;

    for (k = i + 1; k < j; ++k)
      make_edge(i, k, d);
  }
}

void answer()
{
  unsigned last;
  int i;

  last = kth();

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

  if (last == 0)
    __builtin_trap();

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

  csort(ee, eo, 0);
  for (i = 0; i < k; ++i)
      printf("%d\n", ee[i]);
}

void debug()
{
  int i;
  return;
  printf("x2[] : ");
  for (i = 0; i < n; ++i) printf(" %d", x2[i]);
  puts("");
  printf("y2[] : ");
  for (i = 0; i < n; ++i) printf(" %d", y2[i]);
  puts("");

  printf("x3[] : ");
  for (i = 0; i < n; ++i) printf(" %d", x3[i]);
  puts("");
  printf("y3[] : ");
  for (i = 0; i < n; ++i) printf(" %d", y3[i]);
  puts("");
  printf("ii[] : ");
  for (i = 0; i < n; ++i) printf(" %d", ii[i]);
  puts("");
  printf("count(1) = %lld\n",count(1));
  printf("count(10) = %lld\n",count(10));
}

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

Compilation message (stderr)

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

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