Submission #1125297

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125297		sleepntsheep	Road Construction (JOI21_road_construction)	C11	0 / 100	10094 ms	92248 KiB

road_construction

#include <stdio.h>
#include <stdlib.h>

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

#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], L[M], R[M], jj,
    eo;

int x3[N], y3[N];
long long x[N], y[N],
     x2[N], y2[N],
     ee[N * 2];

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

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

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

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

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

int lower_bound(long long *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(long long *a, int n, int 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, long long 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);
}

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 < 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;
    assert_(p_left <= i);
    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 / 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()
{
  int i;
  qsort(x2, n, sizeof *x2, cc);
  qsort(y2, n, sizeof *y2, cc);

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

unsigned kth(int k)
{
  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 max(long long a, long long b)
{
  return a > b ? a : b;
}

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

void make_edge(int i, int j, long long threshold)
{
  long long dd;
  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);
}

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(ii[i], ii[k], d);
  }

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

void answer()
{
  unsigned last;
  int i;

  last = kth(k);

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

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

  qsort(ee, eo, sizeof *ee, cc);
  for (i = 0; i < k; ++i)
      printf("%lld\n", ee[i]);
}

void debug()
{
  int i;
  return;
  printf("x2[] : ");
  for (i = 0; i < n; ++i) printf(" %lld", x2[i]);
  puts("");
  printf("y2[] : ");
  for (i = 0; i < n; ++i) printf(" %lld", 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:142:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |   scanf("%d%d", &n, &k);
      |   ^~~~~~~~~~~~~~~~~~~~~
road_construction.c:145:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |     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