Задача на префиксные суммы

Задача из тренировок по алгоритмам яндекса. Не могу понять почему мое решение не проходит по памяти и как можно его оптимизировать

мой код

with open('input.txt', 'r') as f:
    n, m = map(int, f.readline().split())
    a = list(map(int, f.readline().split()))
    a.sort()
    intervals, max_r = [], 0
    for i in range(m):
        l, r = map(int, f.readline().split())
        intervals.append([l, r])
        max_r = max(max_r, r)
    cats = [0] * (max_r + 1)
    j = 0
    for i in range(max_r + 1):
        while j < len(a) and i == a[j]:
            j += 1
        cats[i] = j

ans = []
for interval in intervals:
    left = interval[0] - 1
    right = interval[1]
    if left >= 0:
        ans.append(cats[right] - cats[left])
    else:
        ans.append(cats[right])
    
print(*ans)
1 лайк

Max_r может быть 10^9, массив cats из 10^9 элементов памяти это слишком много.
Думаю вам стоит попробовать сжать координаты.

Спойлер

(Можно понять что на самом деле большую часть значений которые вы считаете не нужно использовать)

Вообще неплохо было бы если бы сделали раздел “информатика”(Раздел математики), уже вторая задача по инфе.
@Anton

все еще не могу понять какие значение можно удалить :grimacing:

пробовал делать без max_r, но все равно схватывал ML

Ну давай рассмотрим два вида важных позиций:

  1. Позиции где префиксная сумма меняется
  2. Позиции в которых ты запрашиваешь сумму на префиксе.

Вычислять значение в остальных позициях не имеет смысла, так как мы никогда не используем их.

Теперь осталось придумать как использовать эти важные позиции чтобы все работало быстро.

1 лайк
подсказка

Попробуй переместить важные позиции в позиции от 1 до (кол-во важных точек), так чтобы их относительный порядок не изменился, и в них происходило то что происходит в их настоящих позициях.

2 лайка

сделал

1 лайк

в таком случае нужно ещё некоторые темы из раздела робототехники перенести

1 лайк

понял, спасибо! :raised_hands: :raised_hands:

1 лайк