Submission #1124632

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124632		sleepntsheep	허수아비 (JOI14_scarecrows)	C11	100 / 100	2513 ms	71916 KiB

scarecrows

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

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

int n, x[N], y[N], t[N * 2], ll[N],
    A[M], L[M], R[M], ii,
    up[N],
    vv_[99], ll_[99], rr_[99], ii_;
long long ans;

void add(int *v, int l, int r, int p, int k)
{
  if (!*v) 
  {
    *v = ++ii;
    A[*v] = L[*v] = R[*v] = 0;
  }
  A[*v] += k;
  if (l == r)
    return;
  if (p <= (l + r) / 2)
    add(L + *v, l, (l + r) / 2, p, k);
  else
    add(R + *v, (l + r) / 2 + 1, r, p, k);
}
int sum(int v, int l, int r, int x, int y)
{
  if (!v || r < x || y < l)
    return 0;
  if (x <= l && r <= y)
    return A[v];
  return sum(L[v], l, (l + r) / 2, x, y) + sum(R[v], (l + r) / 2 + 1, r, x, y);
}
void generate(int v, int l, int r, int x, int y)
{
  if (!v || r < x || y < l)
    return;
  if (x <= l && r <= y)
  {
    vv_[ii_] = v;
    ll_[ii_] = l;
    rr_[ii_] = r;
    ++ii_;
    return;
  }
  generate(L[v], l, (l + r) / 2, x, y);
  generate(R[v], (l + r) / 2 + 1, r, x, y);
}
int next_(int v, int l, int r, int x, int y)
{
  if (l == r)
    return l;
  if (A[L[v]])
    return next_(L[v], l, (l + r) / 2, x, y);
  return next_(R[v], (l + r) / 2 + 1, r, x, y);
}
int next(int v, int l, int r, int x, int y)
{
  int i;
  ii_ = 0;
  generate(v, l, r, x, y);
  for (i = 0; i < ii_; ++i)
    if (A[vv_[i]])
      return next_(vv_[i], ll_[i], rr_[i], x, y);
  return r;
}

int cx(const void *i, const void *j)
{
  return x[*(int*)i] - x[*(int*)j];
}
int cy(const void *i, const void *j)
{
  return - y[*(int*)i] + y[*(int*)j];
}

void pus(int **eh, int *eo, int x)
{
  int o;
  o = eo[0]++;
  if (!o)
    eh[0] = malloc(2 * sizeof **eh);
  else if (0 == (o & (o - 1)))
    eh[0] = realloc(eh[0], o * 2 * sizeof **eh);
  eh[0][o] = x;
}

void dnc(int l, int r, int *ll, int lo)
{
  int *aa, ao, *bb, bo, *cc, co
      , i, j, m, *aa_, ao_, *bb_, bo_
      , t1, t2;

  if (!lo || l > r)
    return;

  ao = 0;
  bo = 0;
  co = 0;
  ao_ = 0;
  bo_ = 0;
  aa_ = 0;
  bb_ = 0;
  aa = 0;
  bb = 0;
  cc = 0;
  t1 = 0;
  t2 = 0;

  m = (l + r) / 2;

  for (i = 0; i < lo; ++i)
  {
    if (x[ll[i]] <= m)
    {
      pus(&aa, &ao, ll[i]);
      pus(&aa_, &ao_, ll[i]);
    }
    else if (x[ll[i]] > m)
    {
      pus(&bb, &bo, ll[i]);
      pus(&bb_, &bo_, ll[i]);
    }
  }

  for (i = ao - 1; i >= 0; --i)
  {
    up[aa[i]] = next(t1, 0, 1e9, y[aa[i]] + 1, 1e9);
    add(&t1, 0, 1e9, y[aa[i]], 1);
  }

  ii = 0;

  qsort(aa_, ao_, sizeof *aa_, cy);
  qsort(bb_, bo_, sizeof *bb_, cy);

  j = 0;
  for (i = 0; i < ao; ++i)
  {
    while (j < bo_ && y[bb_[j]] > y[aa_[i]])
    {
      while (co && x[cc[co - 1]] > x[bb_[j]])
      {
        add(&t2, 0, 1e9, y[cc[co - 1]], -1);
        --co;
      }
      pus(&cc, &co, bb_[j]);
      add(&t2, 0, 1e9, y[cc[co - 1]], 1);
      ++j;
    }

    ans += sum(t2, 0, 1e9, y[aa_[i]], up[aa_[i]]);
  }

  ii = 0;

  free(cc);
  free(aa_);
  free(bb_);

  if (l < r)
  {
    dnc(l, m, aa, ao);
    dnc(m + 1, r, bb, bo);
  }

  free(aa);
  free(bb);
}

int main()
{
  int i;
  scanf("%d", &n);

  x[n] = 2e9;
  for (i = 0; i < n; ++i)
  {
    scanf("%d%d", x + i, y + i);
    ll[i] = i;
  }
  qsort(ll, n, sizeof *ll, cx);

  dnc(0, 1e9, ll, n);

  printf("%lld", ans);
  return 0;
}

Compilation message (stderr)

scarecrows.c: In function 'main':
scarecrows.c:176:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  176 |   scanf("%d", &n);
      |   ^~~~~~~~~~~~~~~
scarecrows.c:181:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  181 |     scanf("%d%d", x + i, y + i);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 85 / 85