Problem:


Score : 400 points

Problem Statement

There are N one-off jobs available. If you take the i-th job and complete it, you will earn the reward of B_i after A_i days from the day you do it.

You can take and complete at most one of these jobs in a day.

However, you cannot retake a job that you have already done.

Find the maximum total reward that you can earn no later than M days from today.

You can already start working today.

Constraints

All values in input are integers.

1 \leq N \leq 10^5

1 \leq M \leq 10^5

1 \leq A_i \leq 10^5

1 \leq B_i \leq 10^4

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Print the maximum total reward that you can earn no later than M days from today.

Sample Input 1

3 4
4 3
4 1
2 2

Sample Output 1

5

You can earn the total reward of 5 by taking the jobs as follows:

Take and complete the first job today. You will earn the reward of 3 after four days from today.

Take and complete the third job tomorrow. You will earn the reward of 2 after two days from tomorrow, that is, after three days from today.

Sample Input 2

5 3
1 2
1 3
1 4
2 1
2 3

Sample Output 2

10

Sample Input 3

1 1
2 1

Sample Output 3

0



Sample input:
3 4
4 3
4 1
2 2


Sample output:
5

Submission status: Accepted

Solution code:
import heapq as q

def main():
	n,m = map(int, input().split())
	ab = []
	for _ in range(n):
		ab += [list(map(int,input().split()))]
	ab.sort(key=lambda x:x[0])
	hq = []
	index = 0
	ans = 0
	for i in range(1,m+1):
		while True:
			if index == n:
				break
			if ab[index][0] > i:
				break
			q.heappush(hq, -ab[index][1])
			index += 1
		if hq == []:
			continue
		ans += -1*q.heappop(hq)
	print(ans)

main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from collections import deque
from queue import PriorityQueue


def solve(N, M, A, B):
    ans = 0
    # 日付順にソートする
    all_works = deque(sorted(zip(A, B), key=lambda x: x[0]))
    pq = PriorityQueue(maxsize=N)

    for d in range(1, M+1):
        # print('d=', d)
        # 今日が期限の仕事があれば追加
        while all_works and all_works[0][0] == d:
            work = all_works.popleft()
            # 最小値優先なのでマイナスをつける
            pq.put_nowait(-work[1])
        if not pq.empty():
            work = pq.get_nowait()
            ans -= work

    return ans


if __name__ == '__main__':
    N, M = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for idx in range(N):
        A[idx], B[idx] = map(int, input().split())

    ans = solve(N, M, A, B)

    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from collections import deque
from queue import PriorityQueue


def solve(N, M, A, B):
    ans = 0
    # 日付順にソートする
    all_works = deque(sorted(zip(A, B), key=lambda x: x[0]))
    pq = PriorityQueue(maxsize=N)

    for d in range(1, M+1):
        # print('d=', d)
        # 今日が期限の仕事があれば追加
        while all_works and all_works[0][0] == d:
            work = all_works.popleft()
            # 最小値優先なのでマイナスをつける
            pq.put(-work[1])
        if not pq.empty():
            work = pq.get()
            ans -= work

    return ans


if __name__ == '__main__':
    N, M = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for idx in range(N):
        A[idx], B[idx] = map(int, input().split())

    ans = solve(N, M, A, B)

    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from collections import deque
import heapq


def solve(N, M, A, B):
    ans = 0
    # 日付順にソートする
    all_works = deque(sorted(zip(A, B), key=lambda x: x[0]))
    pq = []

    for d in range(1, M+1):
        # print('d=', d)
        # 今日が期限の仕事があれば追加
        while all_works and all_works[0][0] == d:
            work = all_works.popleft()
            # 最小値優先なのでマイナスをつける
            heapq.heappush(pq, -work[1])
        if pq:
            work = heapq.heappop(pq)
            ans -= work

    return ans


if __name__ == '__main__':
    N, M = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for idx in range(N):
        A[idx], B[idx] = map(int, input().split())

    ans = solve(N, M, A, B)

    print(ans)

Submission status: Accepted

Solution code:
import heapq


class Job:

    def __repr__(self):
        return "%d,%d".format(self.days, self.reward)

    def __lt__(self, other):
        return self.reward < other.reward

    def __init__(self, job_id, reward, days):
        self.id = job_id
        self.reward = reward
        self.days = days

N, M = list(map(int, input().split()))
h = []
jobs = []

for i in range(N):
    A, B = list(map(int, input().split()))
    jobs.append(Job(job_id=i, reward=B, days=A))


jobs = sorted(jobs, key=lambda j: j.days)
idx = 0
c = 0

for i in range(1, M+1):
    while idx < N and jobs[idx].days <= i:
        heapq.heappush(h, -jobs[idx].reward)
        idx += 1

    if len(h) != 0:
        c += -heapq.heappop(h)

print(c)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from collections import deque


class PriorityQueue:
    def __init__(self, size):
        self.tree = [None] * size
        self.bottom = 0

    def add(self, data):
        n = self.bottom
        self.bottom += 1
        self.tree[n] = data
        while n != 0:
            parent = (n - 1) // 2
            if self.tree[parent][1] < self.tree[n][1]:
                self.tree[parent], self.tree[n] = (
                    self.tree[n],
                    self.tree[parent],
                )
                n = parent
            else:
                return

    def top(self):
        return self.tree[0]

    def size(self):
        return self.bottom

    def pop_top(self):
        rv = self.tree[0]
        self.tree[0] = self.tree[self.bottom - 1]
        self.bottom -= 1
        n = 0
        while True:
            child1 = 2 * n + 1
            if child1 >= self.bottom:
                return rv
            child2 = 2 * n + 2
            if child2 >= self.bottom:
                child2 = child1

            if (
                self.tree[n][1] > self.tree[child1][1]
                and self.tree[n][1] > self.tree[child2][1]
            ):
                return rv
            elif self.tree[child1][1] > self.tree[child2][1]:
                self.tree[n], self.tree[child1] = (
                    self.tree[child1],
                    self.tree[n],
                )
                n = child1
            else:
                self.tree[n], self.tree[child2] = (
                    self.tree[child2],
                    self.tree[n],
                )
                n = child2
        return rv


def solve(N, M, A, B):
    ans = 0
    # 日付順にソートする
    all_works = deque(sorted(zip(A, B), key=lambda x: x[0]))
    pq = PriorityQueue(N)

    for d in range(1, M+1):
        # print('d=', d)
        # 今日が期限の仕事があれば追加
        while all_works and all_works[0][0] == d:
            work = all_works.popleft()
            pq.add(work)
        # print('all_works', all_works)
        # print('pq=', pq.tree)
        # 優先キューから最優先の仕事を選択する
        if pq.size():
            work = pq.pop_top()
            ans += work[1]

    return ans


if __name__ == '__main__':
    N, M = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for idx in range(N):
        A[idx], B[idx] = map(int, input().split())

    ans = solve(N, M, A, B)

    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from collections import deque


class PriorityQueue:
    def __init__(self, size):
        self.tree = [None] * size
        self.bottom = 0

    def add(self, data):
        n = self.bottom
        self.bottom += 1
        self.tree[n] = data
        while n != 0:
            parent = (n - 1) // 2
            if self.tree[parent][1] < self.tree[n][1]:
                self.tree[parent], self.tree[n] = (
                    self.tree[n],
                    self.tree[parent],
                )
                n = parent
            else:
                return

    def top(self):
        return self.tree[0]

    def size(self):
        return self.bottom

    def pop_top(self):
        rv = self.tree[0]
        self.tree[0] = self.tree[self.bottom - 1]
        self.bottom -= 1
        n = 0
        while True:
            child1 = 2 * n + 1
            if child1 >= self.bottom:
                return rv
            child2 = 2 * n + 2
            if child2 >= self.bottom:
                child2 = child1

            if (
                self.tree[n][1] > self.tree[child1][1]
                and self.tree[n][1] > self.tree[child2][1]
            ):
                return rv
            elif self.tree[child1][1] > self.tree[child2][1]:
                self.tree[n], self.tree[child1] = (
                    self.tree[child1],
                    self.tree[n],
                )
                n = child1
            else:
                self.tree[n], self.tree[child2] = (
                    self.tree[child2],
                    self.tree[n],
                )
                n = child2
        return rv


def solve(N, M, A, B):
    ans = 0
    # 日付順にソートする
    all_works = deque(sorted(zip(A, B), key=lambda x: x[0]))
    pq = PriorityQueue(N)

    for d in range(1, M+1):
        # print('d=', d)
        # 今日が期限の仕事があれば追加
        while all_works and all_works[0][0] == d:
            work = all_works.popleft()
            pq.add(work)
        # print('all_works', all_works)
        # print('pq=', pq.tree)
        # 優先キューから最優先の仕事をする
        if pq.size():
            work = pq.pop_top()
            ans += work[1]

    return ans


if __name__ == '__main__':
    N, M = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for idx in range(N):
        A[idx], B[idx] = map(int, input().split())

    ans = solve(N, M, A, B)

    print(ans)

Submission status: Accepted

Solution code:
import bisect
import time
import heapq


# N: バイトの種類
# M: 日数の最大
N,M = map(int,input().split(" "))

# A 日数
# b バイト代
A = []
B = []
for _ in range(N):
    a,b = map(int,input().split(" "))
    A.append(a)
    B.append(-b)

# 日数でソート
ind_sorted = sorted(range(N), key = lambda x:A[x])
tmp_a = 0
tmp_b_ls = [0]
money = 0
tmp_ind = 0
for i in range(N):
    if A[ind_sorted[i]] > M:
        break
    if tmp_a != A[ind_sorted[i]]:
        # 空いている日数
        # print(d)
        # print(tmp_b_ls)
        d = A[ind_sorted[i]]-tmp_a
        for _ in range(d):
            if tmp_b_ls == []:
                break
            money -= heapq.heappop(tmp_b_ls)
        tmp_a = A[ind_sorted[i]]
    heapq.heappush(tmp_b_ls,B[ind_sorted[i]])

d = M+1-tmp_a
# print(d)
# print(tmp_b_ls)

for _ in range(d):
    if tmp_b_ls == []:
        break
    money -= heapq.heappop(tmp_b_ls)
print(money)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

class HeapQueue:
    def __init__(self,flag): # flag == True 最小値pop / False 最大値pop
        if flag: self.inv = 1
        else: self.inv = -1
        self.hq = []
        heapq.heapify(self.hq)

    def push(self,x):
        heapq.heappush(self.hq,self.inv*x)

    def pop(self):
        return self.inv * heapq.heappop(self.hq)

    def is_empty(self):
        if self.hq:
            return False
        else:
            return True


N,M = inpl()
que = HeapQueue(False)
ABs = [inpl() for _ in range(N)]
ABs.sort()
ABs.append([M+5,0])

itr = 0
ans = 0
for d in range(1,M+1):
    while True:
        A,B = ABs[itr]
        if A > d:
            break
        else:
            que.push(B)
            itr += 1
    if not que.is_empty():
        ans += que.pop()

print(ans)

Submission status: Accepted

Solution code:
import heapq
n,m=list(map(int,input().split()))
tmp=[[] for _ in range(m)]
for i in range(n):
  a,b=list(map(int,input().split()))
  if a<=m:
    tmp[a-1].append(-b)
ans=0
heap=[]
for i in range(m):
  for b in tmp[i]:
    heapq.heappush(heap,b)
  if len(heap)>0:
    ans-=heapq.heappop(heap)
print(ans)

Submission status: Accepted

Solution code:
import heapq
N,M = map(int,input().split())
ls = []
h = []
ans = 0
for n in range(N):
    ls.append(list(map(int,input().split())))
ls = sorted(ls,key=lambda ls:ls[0],reverse=False)
n = 0
for m in range(1,M+1):
    #print (m)
    while(n<N and ls[n][0]<=m ):
        heapq.heappush(h, -ls[n][1])
        n+=1
    if len(h)>0:
        ans -= heapq.heappop(h)
        # print (m,ans)
print (ans)

Submission status: Accepted

Solution code:
import heapq
n,m=map(int, input().split())
s = [list(map(int, input().split())) for i in range(n)]
q = []
ans=0
#ヒープソート
heapq.heapify(s)
for k in range(m-1,-1,-1):
    for i in range(n):
        if len(s)!=0:
            #最小値を返す
            p=heapq.heappop(s)
            if p[0]+k<=m:
                #heappush(list,item) listの葉にitemを追加して小さい要素を上に持ち上げる
                heapq.heappush(q,-p[1])
            else:
                heapq.heappush(s,p)
                break
        else:
            break
    if len(q)!=0:
            #最小値をヒープから取り出す
        p=heapq.heappop(q)
        ans += -p
print(ans)

Submission status: Accepted

Solution code:
import heapq
n,m=map(int, input().split())
s = [list(map(int, input().split())) for i in range(n)]
q = []
ans=0
#ヒープソート
heapq.heapify(s)
for k in range(m-1,-1,-1):
    while True:
        if len(s)!=0:
            #最小値を返す
            p=heapq.heappop(s)
            if p[0]+k<=m:
                #heappush(list,item) listの葉にitemを追加して小さい要素を上に持ち上げる
                heapq.heappush(q,-p[1])
            else:
                heapq.heappush(s,p)
                break
        else:
            break
    if len(q)!=0:
            #最小値をヒープから取り出す
        p=heapq.heappop(q)
        ans += -p
print(ans)

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
q = []
heapq.heapify(q)
heapq.heapify(ab)
total = 0
for i in range(m, -1, -1):
    while True:
        if len(ab) != 0:
            p = heapq.heappop(ab)
            if p[0] + i <= m:
                heapq.heappush(q, -p[1])
            else:
                heapq.heappush(ab, p)
                break
        else:
            break
    if len(q) != 0:
        p = heapq.heappop(q)
        total += -p
print(total)

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
work = [[0] for _ in range(M + 1)]
for _ in range(N):
  d, p = map(int, input().split())
  if d > M: continue
  work[d].append(-p)
#print(work)
money = 0
q = work[1]
heapq.heapify(q)
for i in range(1, M + 1):
  #print(q)
  if len(q) != 0:
    money += heapq.heappop(q)
  if i == M: continue
  for p in work[i + 1]:
    heapq.heappush(q, p)
print(-money)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import heapq
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,M = IL()
ab = [IL() for i in range(N)]
data = [[] for i in range(M+1)]
able = []

hpop = heapq.heappop
hpush = heapq.heappush

for d,v in ab:
  if d > M:
    continue
  else:
    data[d].append(-v)

ans = 0
for i in range(1,M+1):
  if data[i] == 0:
    continue
  else:
    #print(data[i])
    for l in data[i]:
      hpush(able,l)
  #print(able)
  if able:
    ans -= hpop(able)
    #print(ans)

print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc137/submissions/6836579

from heapq import heappush, heappop

n, m = map(int, input().split())
c = [[] for _ in range(m)]
for _ in range(n):
    a, b = map(int, input().split())
    if a <= m:
        c[a - 1].append(b)
r = 0
h = []
for l in c:
    # m - c[i + 1] 日の仕事選びをする
    for x in l:
        # 条件に間に合う仕事を h に入れていく
        heappush(h, -x)
    # もし仕事があるなら最大の仕事をチョイスして h から削除
    if h:
        r -= heappop(h)
print(r)

Submission status: Accepted

Solution code:
from collections import deque
import heapq

n, m = map(int, input().split(' '))
works = [[] for _ in range(100001)]

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

ans = 0
h = []
for day in range(1, m + 1):
    for gain in works[day]:
        heapq.heappush(h, -gain)


    if h:
        gain = -heapq.heappop(h)
        ans += gain


print(ans)

Submission status: Accepted

Solution code:
import heapq
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, M = map(int, input().split())
works = [list(map(int, input().split())) for _ in range(N)]

heapq.heapify(works)

cand = []

day = 1
ans = 0
while day <= M:
    while works:
        a, b = heapq.heappop(works)
        if a <= day:
            heapq.heappush(cand, -b)
        else:
            heapq.heappush(works, [a, b])
            break
    if len(cand) > 0:
        ans -= heapq.heappop(cand)
    day += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
imput = sys.stdin.readline

def main():
    n,m = map(int,input().split())
    money = [[] for _ in range(10**5)]
    dp = [0] * m
    hq = []
    heapq.heapify(hq)

    for _ in range(n):
        a,b = map(int,input().split())
        money[a-1] += [b]

    for i in range(m):
        for j in money[i]:
            heapq.heappush(hq,-j)
        if hq:
            dp[i] += -heapq.heappop(hq)
        if i >= 1:
            dp[i] += dp[i-1]
    print(dp[-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
AB.sort(key=lambda x:x[0])

res = 0
q = []
pos = 0
heapq.heapify(q)
for i in range(1,M+1):
    x = 0
    #queueへの追加
    while pos <= N-1:
        if AB[pos][0] <= i:
            heapq.heappush(q,AB[pos][1]*-1)
            pos += 1
        else:
            break
    #queueからの取り出し
    if len(q) != 0:
        x = heapq.heappop(q)
    res += x*-1
print(res)

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
q = []
heapq.heapify(q)
heapq.heapify(ab)
total = 0
for i in range(m, -1, -1):
    while True:
        if len(ab) != 0:
            p = heapq.heappop(ab)
            if p[0] + i <= m:
                heapq.heappush(q, -p[1])
            else:
                heapq.heappush(ab, p)
                break
        else:
            break
    if len(q) != 0:
        p = heapq.heappop(q)
        total += -p
print(total)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

h = []

ans = 0

ab.sort()
i = 0
for d in range(1, m+1):
    while i < n:
        if ab[i][0] <= d:
            heappush(h, - ab[i][1])
            i += 1
        else:
            break
    if len(h) > 0:
        ans -= heappop(h)

print(ans)

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
tmp = [[] for _ in range(m)]
for j in range(n):
    a, b = list(map(int, input().split()))
    if a-1 < m:
        tmp[a-1].append(-b) #heapqはMin Heapのみ

ans = 0
heap = []
for i in range(m):
    for b in tmp[i]:
        heapq.heappush(heap, b)
    if len(heap) > 0:
        ans -= heapq.heappop(heap)
print(ans)

Submission status: Accepted

Solution code:
import heapq

N, M = [int(_) for _ in input().split()]
ABs = [[] for _ in range(M + 1)]
r = 0

for i in range(N):
    A, B = [int(x) for x in input().split()]
    if A <= M:
        ABs[A].append(-B)

q = []

for m in range(1, M + 1):
    if ABs[m] != 0:
        for b in ABs[m]:
            heapq.heappush(q, b)

    if len(q) != 0:
        r -= heapq.heappop(q)

print(r)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
inpl = lambda: list(map(int,input().split()))

class SegmentTree:
    def __init__(self, value, N=0, comp=lambda x,y: x<=y, reverse=False):
        M = max(len(value),N)
        N = 2**(len(bin(M))-3)
        if N < M: N *= 2
        self.N = N
        self.node = [0] * (2*N-1)
        for i in range(N):
            self.node[N-1+i] = i
        self.value = [None] * N
        for i, v in enumerate(value):
            self.value[i] = v
        self.comp = lambda x, y: True if y is None else False if x is None else comp(x,y)^reverse
        for i in range(N-2,-1,-1):
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            if self.comp(left_v, right_v):
                self.node[i] = left_i
            else:
                self.node[i] = right_i

    def set_input(self, n, v):
        self.value[n] = v
        i = (self.N-1) + n
        while i > 0:
            i = (i-1)//2
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            if self.comp(left_v, right_v):
                new_i = left_i
            else:
                new_i = right_i
            if new_i == self.node[i] and new_i != n:
                break
            else:
                self.node[i] = new_i

    def get_input(self, n):
        if n is None:
            return None
        else:
            return self.value[n]

    def get_output(self, a=0, b=-1):
        return self.get_input(self.get_output_index(a,b))

    def get_output_index(self,
                         a=0, b=-1,
                         k=0, l=0, r=-1):
        if b < 0:
            b = self.N
        if r < 0:
            r = self.N
        if a <= l and r <= b:
            return self.node[k]
        elif r <= a or b <= l:
            return None
        else:
            left_i = self.get_output_index(a,b,2*k+1,l,(l+r)//2)
            right_i = self.get_output_index(a,b,2*k+2,(l+r)//2,r)
            left_v, right_v = self.get_input(left_i), self.get_input(right_i)
            if left_v is None and right_v is None:
                return None
            elif self.comp(left_v, right_v):
                return left_i
            else:
                return right_i

N, M = inpl()
AB = [ inpl() for _ in range(N) ]
AB.sort()
A = [ ab[0] for ab in AB ]
B = [ ab[1] for ab in AB ]
sg = SegmentTree(B, reverse=True)
ans = 0
n = 0
for m in range(1,M+1):
    while n < N and A[n] <= m:
        n += 1
    p = sg.get_output_index(0, n)
    if p is not None:
        ans += sg.get_input(p)
        sg.set_input(p, None)
print(ans)

Submission status: Accepted

Solution code:
import bisect
import sys
input = sys.stdin.readline
inpl = lambda: list(map(int,input().split()))

class SegmentTree:
    def __init__(self, value, N=0, comp=lambda x,y: x<=y, reverse=False):
        M = max(len(value),N)
        N = 2**(len(bin(M))-3)
        if N < M: N *= 2
        self.N = N
        self.node = [0] * (2*N-1)
        for i in range(N):
            self.node[N-1+i] = i
        self.value = [None] * N
        for i, v in enumerate(value):
            self.value[i] = v
        self.comp = lambda x, y: True if y is None else False if x is None else comp(x,y)^reverse
        for i in range(N-2,-1,-1):
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            if self.comp(left_v, right_v):
                self.node[i] = left_i
            else:
                self.node[i] = right_i

    def set_input(self, n, v):
        self.value[n] = v
        i = (self.N-1) + n
        while i > 0:
            i = (i-1)//2
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            if self.comp(left_v, right_v):
                new_i = left_i
            else:
                new_i = right_i
            if new_i == self.node[i] and new_i != n:
                break
            else:
                self.node[i] = new_i

    def get_input(self, n):
        if n is None:
            return None
        else:
            return self.value[n]

    def get_output(self, a=0, b=-1):
        return self.get_input(self.get_output_index(a,b))

    def get_output_index(self,
                         a=0, b=-1,
                         k=0, l=0, r=-1):
        if b < 0:
            b = self.N
        if r < 0:
            r = self.N
        if a <= l and r <= b:
            return self.node[k]
        elif r <= a or b <= l:
            return None
        else:
            left_i = self.get_output_index(a,b,2*k+1,l,(l+r)//2)
            right_i = self.get_output_index(a,b,2*k+2,(l+r)//2,r)
            left_v, right_v = self.get_input(left_i), self.get_input(right_i)
            if left_v is None and right_v is None:
                return None
            elif self.comp(left_v, right_v):
                return left_i
            else:
                return right_i

N, M = inpl()
AB = [ inpl() for _ in range(N) ]
AB.sort()
A = [ ab[0] for ab in AB ]
B = [ ab[1] for ab in AB ]
sg = SegmentTree(B, reverse=True)
ans = 0
n = 0
for m in range(1,M+1):
    n = bisect.bisect_right(A, m, lo=n)
    p = sg.get_output_index(0, n)
    if p is not None:
        ans += sg.get_input(p)
        sg.set_input(p, None)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
from collections import defaultdict
N,M = map(int,input().split())
jobs = defaultdict(list)
for i in range(N):
    a,b = map(int,input().split())
    if a <= M: jobs[a-1].append(b)
h = []
ans = 0
for i in range(M):
    if jobs[i]:
        for j in jobs[i]:
            heappush(h, -j)
    if len(h) > 0:
        ans += -heappop(h)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import heapq

N, M = map(int, str(input()).split())
job_list = [list(map(int, input().split())) for i in range(N)]

# 日数と報酬のDictにまとめ直す
job_dict = dict()
for job in job_list:
    job_dict.setdefault(job[0], []).append(job[1])

# 残り日数に収まる最大の日数で、最大もらえる報酬を足して行く
# 残り日数が厳しい方から求めていく
result = 0
heap = []
for days in range(1, M + 1):
    if days in job_dict:
        for v in job_dict[days]:
            heapq.heappush(heap, -v)
    if len(heap) != 0:
        result -= heapq.heappop(heap)

print(result)

Submission status: Accepted

Solution code:
import heapq

N,M = map(int,input().split())

tasks = [[] for _ in range(100001)]
#tasks = [[] for _ in range(11)]
for n in range(N):
	A,B = map(int,input().split())
	tasks[A].append(B)
#print(tasks)

ans = 0
h = []
for day in range(1,M+1):
	for gain in tasks[day]:
		heapq.heappush(h,-gain)
	#print(h)
	if h:
		gain = -heapq.heappop(h)
		#print('\t{:02d}: gain={}'.format(day,gain))
		ans += gain
print(ans)

Submission status: Accepted

Solution code:
import heapq
n,m=map(int,input().split())
ab=[]
for i in range(m+1):
    ab.append([])
for i in range(n):
    a,b=map(int,input().split())
    if a>m:
        continue
    ab[a].append(b)
h = []
s=0
for i in range(1,m+1):
    for v in ab[i]:
        heapq.heappush(h,-1*v)
    if len(h)>0:
        s+=-1*heapq.heappop(h)
print(s)

Submission status: Accepted

Solution code:
import heapq
n,m=map(int,input().split())
ab=[]
for i in range(m+1):
    ab.append([])
for i in range(n):
    a,b=map(int,input().split())
    if a<=m:
        ab[a].append(b)
h = []
s=0
for i in range(1,m+1):
    for v in ab[i]:
        heapq.heappush(h,-1*v)
    if len(h)>0:
        s+=-1*heapq.heappop(h)
print(s)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
b_list=[[] for i in range(m)]
for i in range(n):
    a,b=map(int,input().split())
    if a<=m:
        b_list[a-1].append(b)
import heapq
p=[]
ans=0
for i in range(m):
    if b_list[i]==[]:
        pass
    else:
        for j in b_list[i]:
            heapq.heappush(p,-j)
    if len(p)!=0:
        now=-heapq.heappop(p)
        ans+=now
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq 
input = sys.stdin.readline
n,m = map(int,input().split())
l=[tuple(map(int,input().split())) for i in range(n)]
l.sort(reverse=True)

w = []
hpop = heapq.heappop
hpush = heapq.heappush
ans = 0

for i in range(1,m+1):
  while l and l[-1][0]==i:
    hpush(w,-l.pop()[1])
  if w:
    ans += hpop(w)
print(-ans)

Submission status: Accepted

Solution code:
import heapq
import numpy as np

N, M = [int(a) for a in input().split()]

jobs = [[] for _ in range(M)]

for _ in range(N):
    a, b = map(lambda x: int(x), input().split())
    if a > M:
      continue
    jobs[M-a].append(b)

heap = []
ans = 0
for i in range(M-1, -1, -1):
    for b in jobs[i]:
        # 降順にするためにマイナスをつけて入れる
        heapq.heappush(heap, -b)
    if len(heap) != 0:
        # 取り出した値にマイナスをつけて元に戻す
        ans += -heapq.heappop(heap)
print(ans)

Submission status: Accepted

Solution code:
import heapq

n,m=map(int,input().split())
l=[[] for i in range(m)]
s=[]
for i in range(n):
   a,b=map(int,input().split())
   if a<=m:
     l[a-1].append(b)

t=0
heapq.heapify(s)

for i in range(m):
  for j in range(len(l[i])):
    heapq.heappush(s,-l[i][j])
  if len(s)>0:
    t-=heapq.heappop(s)

print(t)

Submission status: Accepted

Solution code:
import heapq
n,m = [int(i) for i in input().split()]

l = [list(map(int, input().split())) for _ in range(n)]
l.sort(reverse = True)

# 昇順降順のキー指定する方法
#l = sorted(l,key = lambda x :(-x[1],-x[0]))

ret = 0
pay = []
for d in range(1,m+1):
    while l and l[-1][0] <= d:
        tmp = l.pop()
        #最大値から取り出したいので-1をかけている
        heapq.heappush(pay,-tmp[1])
    if pay:
        ret -= heapq.heappop(pay) 

print(ret)

Submission status: Accepted

Solution code:
#coding utf-8
import heapq
N,M=map(int,input().split())
AB= [[int(i) for i in input().split()] for i in range(N)]
AB.sort(reverse=True)
work=[]
heapq.heapify(work)
ans=0
for i in range(1,M+1):
  while AB and AB[-1][0] <=i:
      tmp=AB.pop()
      heapq.heappush(work,-tmp[1])
  if work:
    tmp=heapq.heappop(work)
    ans-=tmp
  
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq

N,M = map(int,input().split())

l = defaultdict(list)
for i in range(N):
    A,B = map(int,input().split())
    l[A].append(-B)

h = []
ans = 0
for i in range(M):
    for B in l[i+1]:
        heapq.heappush(h,B)
    if len(h)!=0:
        ans += - heapq.heappop(h)
print(ans)

Submission status: Accepted

Solution code:
import heapq
def main(n,m,c):
    cost_map = dict([(i, [])for i in range(1,m+1)])
    for a, b in c:
        if a <= m:
            cost_map[a].append(b)
        
    hp =[]
    ret = 0
    for i in range(1, m+1):
        costs = cost_map[i]
        [heapq.heappush(hp, -c) for c in costs]
        if(len(hp) > 0):
            c = heapq.heappop(hp)
            ret -= c
    return ret
if __name__ == "__main__":
    n,m = map(lambda x: int(x), input().strip().split())
    c = [ list(map(lambda x: int(x), input().strip().split())) for i in range(n)]
    print(main(n,m,c))

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
AB = [[] for _ in range(M)]
que = []
for _ in range(N):
    a, b = map(int, input().split())
    if a <= M:
        AB[a-1].append(b)

ans = 0
for i in range(M):
    for b in AB[i]:
        heapq.heappush(que, -b)
    if len(que) > 0:
        ans += -heapq.heappop(que)
print(ans)