Python-сообщество

Не могу пройти 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)

Отредактировано udeep (Дек. 2, 2019 23:23:32)

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

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

Отредактировано doza_and (Дек. 4, 2019 06:52:57)

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

  
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)

Отредактировано udeep (Дек. 4, 2019 09:36:07)