DjangoBB LoFi version

Полная версия: Points and intervals - Time limit exceeded

Начало » Python для новичков » Points and intervals - Time limit exceeded

udeep

Дек. 2, 2019 22:37:55

Не могу пройти 7 тест задания:
The first line contains the two integers: 1≤n≤50000 and 1≤m≤50000 — the amount of intervals and points on the straight line, respectively. Next n lines each contain the two integers ai and bi (ai≤bi) — the coordinates of interval ends. The last line contains m integers — points positions. All coordinates do not exceed 10**8 by absolute value. The point is considered belonging to the specified interval, if it lies inside this interval or on the interval boundary. For each of the points output to how many intervals it belongs to, in the order of occurence of these points in the input.

Очень вероятно, что мой код в данном тесте “валится” по лимиту времени (3 секунды) от множественного повторения одинаковых точек…

   
from bisect import bisect, bisect_left
from collections import Counter
  
  
n, m = map(int, input().split())
intervals = Counter(tuple(map(int, input().split())) for _ in range(n))
points = tuple(sorted((v, i) for i, v in enumerate(map(int, input().split())))) 
  
result = [0 for _ in range(m)]
for (x, y), k in intervals.items():
    for _, i in points[bisect_left(points, (x, -1)) : bisect(points, (y, m))]:
        result[i] += k
          
print(*result)

- Прошу подсказать, как оптимально сгруппировать точки с возможностью быстрого вывода их вхождений в интервалы.

py.user.next

Дек. 4, 2019 02:29:09

А ты пробовал взять каждый интервал и пройти по каждой точке, увеличив количество на точке, если эта точка входит в этот интервал?

doza_and

Дек. 4, 2019 06:48:16

udeep
как оптимально сгруппировать точки

py.user.next дело говорит. Если быть ближе к формулировке исходной задачи то можно ввести программные сущности - точки. Они бывают 3 видов - начало интервала, конец интервала и обычные точки. Если точки отсортировать (по координате, при одинаковых координатах начало интервала меньше обычной точки а конец больше) то новая группа точек начинается при извлечении начала или конца интервала.

Данный способ конечно не оптимальный, поскольку обычные точки отсортируются внутри группы, а это не требуется.

udeep

Дек. 4, 2019 09:35:58

Спасибо за указание верного пути…

  
E = 50000 + 1
F = -E
   
n, m = map(int, input().split())
line = []
for _ in range(n):
    i, j = map(int, input().split())
    line.extend([(i, F), (j, E)])
for i, v in enumerate(map(int, input().split())):
    line.append((v, i))
 
line.sort()
results = [0] * m
r = 0
for v, i in line:
    if i == F:
        r += 1
    elif i == E:
        r -= 1
    else:
        results[i] = r 
 
print(*results)