Submission #1124722

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124722		sleepntsheep	버스 (JOI14_bus)	C11	35 / 100	304 ms	86560 KiB

bus

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

#define N 100000
#define M 300000
#define P (1 << 25)

int n, m, q, pool,
    a[M], b[M], x[M], y[M], ii[N],
    Lj,
    t[N],
    A[P], L[P], R[P];

int min(int i, int j)
{
  return i < j ? i : j;
}

int max(int i, int j)
{
  return i > j ? i : j;
}

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

void add(int *v, int l, int r, int p, int k)
{
  if (!*v)
  {
    *v = ++pool;
    A[*v] = -1;
  }
  if (k > A[*v])
    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 query(int v, int l, int r, int x, int y)
{
  if (!v || r < x || y < l)
    return -1;
  if (x <= l && r <= y)
    return A[v];
  return max(query(L[v], l, (l + r) / 2, x, y)
            , query(R[v], (l + r) / 2 + 1, r, x, y));
}

int main()
{
  int i, j;

  scanf("%d%d", &n, &m);
  for (i = 0; i < m; ++i)
  {
    scanf("%d%d%d%d", a + i, b + i, x + i, y + i);
    ii[i] = i;
  }
  qsort(ii, m, sizeof *ii, compare_by_arrival_time);

  for (i = 0; i < m; ++i)
  {
    j = ii[i];
    if (1 == a[j])
      add(t + b[j], 0, 1e8, y[j], x[j]);
    else
      add(t + b[j], 0, 1e8, y[j], query(t[a[j]], 0, 1e8, 0, x[j]));
  }

  scanf("%d", &q);
  while (q--)
  {
    scanf("%d", &Lj);
    printf("%d\n", query(t[n], 0, 1e8, 0, Lj));
  }

  return 0;
}

Compilation message (stderr)

bus.c: In function 'main':
bus.c:60:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |   scanf("%d%d", &n, &m);
      |   ^~~~~~~~~~~~~~~~~~~~~
bus.c:63:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |     scanf("%d%d%d%d", a + i, b + i, x + i, y + i);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bus.c:77:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |   scanf("%d", &q);
      |   ^~~~~~~~~~~~~~~
bus.c:80:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |     scanf("%d", &Lj);
      |     ^~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 15 / 15
• Subtask 3: 0 / 15
• Subtask 4: 0 / 50