Problem p02948 (python)

Fixed submission:
import heapq
#これを加える！！！！
def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt

n, m = map(int, input().split(' '))
income = []
for i in range(10**5+1):
  income.append([])
ans = 0

for i in range(n):
  a, b = map(int, input().split(' '))
  income[a].append(b)

# print(n, m)
# print(income)

# tmp = sorted(income, key=lambda x: x[0], reverse=True)
# sorted_income = sorted(tmp, key=lambda x: x[1], reverse=True)

# print(sorted_income)

heap = []
for i in range(1, m+1):
  values = income[i]
  for j in range(len(values)):
    _heappush_max(heap, values[j])
  
  if len(heap) < 1:
    continue
  
  max_value = _heappop_max(heap)
  if max_value:
    ans += max_value
  # print(ans)
  

print(ans)

Buggy submission (verdict: Runtime Error):
import heapq
#これを加える！！！！
def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt

n, m = map(int, input().split(' '))
income = []
for i in range(10**5):
  income.append([])
ans = 0

for i in range(n):
  a, b = map(int, input().split(' '))
  income[a].append(b)

# print(n, m)
# print(income)

# tmp = sorted(income, key=lambda x: x[0], reverse=True)
# sorted_income = sorted(tmp, key=lambda x: x[1], reverse=True)

# print(sorted_income)

heap = []
for i in range(1, m+1):
  values = income[i]
  for j in range(len(values)):
    _heappush_max(heap, values[j])
  
  if len(heap) < 1:
    continue
  
  max_value = _heappop_max(heap)
  if max_value:
    ans += max_value
  # print(ans)
  

print(ans)

Buggy submission (verdict: Runtime Error):
import heapq
#これを加える！！！！
def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt

n, m = map(int, input().split(' '))
income = []
for i in range(10**5):
  income.append([])
ans = 0

for i in range(n):
  a, b = map(int, input().split(' '))
  income[a].append(b)

# print(n, m)
# print(income)

# tmp = sorted(income, key=lambda x: x[0], reverse=True)
# sorted_income = sorted(tmp, key=lambda x: x[1], reverse=True)

# print(sorted_income)

heap = []
for i in range(1, m+1):
  values = income[i]
  for j in range(len(values)):
    _heappush_max(heap, values[j])
  
  if len(heap) < 1:
    continue
  
  max_value = _heappop_max(heap)
  if max_value:
    ans += max_value
  # print(ans)
  

print(ans)