Информация об изменениях

Сообщение Re[2]: Отрезки и точки. Считать вхождение. от 18.02.2021 12:42

Изменено 18.02.2021 13:33 watchmaker

Старый текст
Новый текст
Разница

Re[2]: Отрезки и точки. Считать вхождение.

Здравствуйте, Sharov, Вы писали:

S>Никто не поможет? Задача(формулировка) вроде простая -- даны начала отрезков (массив), конец отрезков (массив)
S>и точки (массив). Для каждой точки посчитать число интервалов, куда она входит.

Ту же понимаешь, что формулировку задачи нужно было написать в первом же сообщении?
Там вместо этого написано, что ты что-то сделал и что это не работает. Предлагаешь другим догадываться, что именно нужно было сделать и в чём была ошибка?

Вообще, раз у тебя все запросы доступны заранее, то это типичная offline-задача: их часто можно гораздо быстрее решить, если не обрабатывать каждый запрос по отдельности (как в online), а делать их кучей.
Тут достаточно слить все три входящих массива в один и отсортировать его.

…





def count_segments(starts: List[int], ends: List[int], points: List[int]):
  # замкнутый интервал
  S, E, Q = 0, 2, 1  # [u, v]
  # варианты для открытых/полуоткрытых интервалов
  # S, E, Q = 2, 0, 1  # (u, v)
  # S, E, Q = 0, 1, 2  # [u, v)

  a = []
  for b, l in ((S, starts), (E, ends), (Q, points)):
    a.extend((i << 2) | b for i in l)
  a.sort()
  c = 0
  d = {}
  for v in a:
    t = v & 3
    if t == S:
      c += 1
    elif t == E:
      c -= 1
    elif t == Q:
      p = v >> 2
      d[p] = c  # тут можно ещё быстрее, если убрать промежуточный хещ-массив, а сразу хранить индекс точки, куда нужно записать ответ
    else:
      assert False
  return [d[p] for p in points]

Re[2]: Отрезки и точки. Считать вхождение.

…





def count_segments(starts: List[int], ends: List[int], points: List[int]):
  # замкнутый интервал
  S, E, Q = 0, 2, 1  # [u, v]
  # варианты для открытых/полуоткрытых интервалов
  # S, E, Q = 2, 0, 1  # (u, v)
  # S, E, Q = 0, 1, 2  # [u, v)

  a = []
  for b, l in ((S, starts), (E, ends), (Q, points)):
    a.extend((i << 2) | b for i in l)
  a.sort()
  c = 0
  d = {}
  for v in a:
    t = v & 3
    if t == S:
      c += 1
    elif t == E:
      c -= 1
    elif t == Q:
      p = v >> 2
      d[p] = c  # тут можно ещё быстрее, если убрать промежуточный хещ-массив, а сразу хранить индекс точки, куда нужно записать ответ
    else:
      assert False
  return [d[p] for p in points]