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:
#!/usr/bin/env python3
import sys
import collections
from operator import itemgetter
import heapq


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):

    jobs_time = collections.defaultdict(list)
    for a,b in zip(A,B):
        jobs_time[b].append(a)

    jobs_time = sorted(jobs_time.items(),reverse=True)
    job_list = [0] * M

    for k,v in jobs_time: 
        v.sort()
        st = -1
        for vv in v:
            if vv <= M:
                for i in range(max(st,vv-1),len(job_list)):
                    if job_list[i] < k:
                        job_list[i] = k
                        st = min(i+1,len(job_list))
                        break
            else:
                break

        if all(j>0 for j in job_list):
            break

    print(sum(job_list))

    return

def solve2(N: int, M: int, A: "List[int]", B: "List[int]"):
    jobs_time = []
    for a,b in zip(A,B):
        jobs_time.append((b,a))

    jobs_time = sorted(jobs_time,key=itemgetter(0,1),reverse=True)
    #jobs_time = sorted(jobs_time,key=lambda x: -x[0]*10**6+x[1])
    job_list = [0] * M
    job_cnt = 0
    res = 0
    end = len(job_list)
    for b,a in jobs_time: 
        if a <= M:
            for i in range(a-1,end):
                if job_list[i] < b:
                    if job_list[i] == 0:
                        job_cnt += 1
                    else:
                        res -= job_list[i]
                    job_list[i] = b
                    res += b
                    break
            if job_cnt >= len(job_list):
                break

            for i in range(end-1,-1,-1):
                if job_list[i] == 0:
                    end = i + 1
                    break

    print(res)

def solve3(N: int, M: int, A: "List[int]", B: "List[int]"):
    jobs_time = []
    for a,b in zip(A,B):
        jobs_time.append((a,b))
    jobs_time = sorted(jobs_time,key=itemgetter(0))

    job_list = []
    res = 0
    js = 0
    #print(jobs_time)
    for i in range(M):
        for j in range(js,N):
            if jobs_time[j][0] == (i+1):
                heapq.heappush(job_list,(- jobs_time[j][1], jobs_time[j][1]))
            elif jobs_time[j][0] > (i+1):
                js = j
                break

        if len(job_list) > 0:
            _,b = heapq.heappop(job_list)
            res += b

    print(res)



# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]" 
    B = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve3(N, M, A, B)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq

n, m = [int(v) for v in input().split()]
ab_ = [[int(v) for v in input().split()] for _ in range(n)]

ab = sorted(ab_, key=lambda x: (x[0], x[1])) 
#print(ab)
ans = 0

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

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)]
AB.sort()
h = []
i = 0
ans = 0
for m in range(M-1,-1,-1):
    while i<N and AB[i][0]+m <= M:
        heapq.heappush(h,-AB[i][1])
        i += 1
    if len(h) != 0:
        ans -= heapq.heappop(h)

print(ans)

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
a_b = [[] for _ in range(m)]
for i in range(n):
    a, b = map(int, input().split())
    if a < m+1:
        a_b[a-1].append(-b)
h = []
heapq.heapify(h)
ans = 0
for i in range(m):
    for j in a_b[i]:
        heapq.heappush(h, j)
    if len(h) == 0:
        continue
    ans += heapq.heappop(h)*(-1)
print(ans)

Submission status: Accepted

Solution code:
import heapq
N,M = map(int,input().split())
AB = list(list(map(int,input().split()))for i in range(N))
AB.sort()
can = []
p = 0
ans = 0
for i in range(M+1):
    while p<N and (AB[p][0] <= i) :
        heapq.heappush(can,-AB[p][1])
        p += 1
        
    if can != []:
        ans += heapq.heappop(can)
print(-ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heappush,heappop

n, m = map(int, sys.stdin.readline().split())
d = [[] for _ in range(m+1)]
for i in range(n):
    a, b = map(int, sys.stdin.readline().split())
    if a <= m:
        d[a].append(b)

res = 0
resList = []
for i in range(1, m+1):
    if len(d[i]) > 0:
        for j in d[i]:
            heappush(resList, -j)
    if len(resList) > 0:
        res += (-1) * resList[0]
        heappop(resList)

print(res)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import heapq
from collections import defaultdict


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    # for d in range(M): d日以内に終わる仕事で残っている最大のものを受ける
    L = [] # d日以内に終わる最大のしごと
    Q = defaultdict(list)
    for a, b in zip(A, B):
        heapq.heappush(Q[a], -b)
    
    res = 0
    for d in range(1, M+1):
        for b in Q[d]:
            heapq.heappush(L, b)
        if len(L) == 0:
            continue
        b = heapq.heappop(L)
        res -= b

    print(res)


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]" 
    B = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
import sys
import heapq
import math

sys.setrecursionlimit(100000)

MIN = -10 ** 9
MAX = 10 ** 9 + 7


def main():
    # N = int(input())
    N, M = [int(a) for a in input().split()]
    AB = [
        [int(a) for a in input().split()]
        for _ in range(N)
    ]

    # AB = sorted(AB, key=lambda it: it[1])

    ARR = [[] for _ in range(M + 1)]
    for a, b in AB:
        if a > M:
            continue
        ARR[a].append(b)
    # print("ARR", ARR)

    res = 0
    q = []
    for i in range(1, M + 1):
        current = ARR[i]
        for a in current:
            heapq.heappush(q, -a)
        if len(q) != 0:
            res -= heapq.heappop(q)
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from heapq import heappop, heappush

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    d = defaultdict(list)
    for _ in range(N):
        a, b = map(int, input().split())
        d[a].append(-b)

    ans = 0
    heap = []
    for i in range(1, M+1):
        for b in d[i]:
            heappush(heap, b)
        if heap:
            ans -= heappop(heap)

    return ans


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:

N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
import heapq
AB.sort()
heap = []
heapq.heapify(heap)
ans = 0
i = 0
day = 1
while day <= M:
    while i < N and AB[i][0] <= day:
        heapq.heappush(heap,-AB[i][1])
        i += 1
    day += 1
    if not(heap):continue
    ans -= heapq.heappop(heap)

print(ans)

Submission status: Accepted

Solution code:
import heapq
from collections import deque

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

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

wq = deque(sorted(work))

paytree = []

ans = 0

for day in range(M + 1):
    while len(wq) > 0 and wq[0][0] <= day:
        heapq.heappush(paytree, wq.popleft()[1] * (-1))
    if len(paytree) > 0:
        ans -= heapq.heappop(paytree)

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB = sorted(sorted(AB, key=lambda x: x[0], reverse=False), key=lambda x: x[1], reverse=True)
x = [0] * M
p = [x for x in range(M)]

cnt = 0
cntIN = M
for a, b in AB:
    i = M-a

    s = []
    while i >= 0 and p[i] != i:
        s.append(i)
        i = p[i]
    for j in s:
        p[j] = i - 1

    if i >= 0:
        x[i] = b
        p[i] = i - 1
        cntIN -= 1            
        if cntIN <= 0:
            break

print(sum(x))

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heapify, heappop, heappush
from sys import stdin

def main():
    N, M = map(int, input().split())
    AB = [tuple(map(int, input().split())) for _ in [0] * N]

    ab = defaultdict(list)
    for a, b in AB:
        ab[a].append(b)

    ans = 0
    reward = []
    for i in range(1, M + 1):
        if ab[i]:
            for n in ab[i]:
                heappush(reward, n * -1)
        if reward:
            ans += heappop(reward) * -1
    print(ans)

input = lambda: stdin.readline()
main()

Submission status: Accepted

Solution code:
import heapq

n, m = map(int, input().split())

# delay, reword
jobs = [list(map(int, input().split())) for i in range(n)]
jobs_days = [[] for i in range(m)]
for job in jobs:
    if job[0] - 1 < m:
        jobs_days[job[0] - 1].append(-job[1])

reward = 0
h = []
heapq.heapify(h)

for i in range(m):
    for job in jobs_days[i]:
        heapq.heappush(h, job)
    if len(h) > 0:
        reward += heapq.heappop(h)

print(-reward)

Submission status: Accepted

Solution code:

import sys
from operator import attrgetter
import heapq

def main():
    N,M = [int(i) for i in sys.stdin.readline().strip().split()]
    works = [[] for i in range(10**5+1)]
    ans = 0
    for i in range(N):
        A,B = [int(i) for i in sys.stdin.readline().strip().split()]
        heapq.heappush(works[A], -B)
    
    avaiable_works = []
    for i in range(1, M+1):
        for item in works[i]:
            heapq.heappush(avaiable_works, item)
        if len(avaiable_works) > 0:
            revenue = abs(heapq.heappop(avaiable_works))
        else:
            continue
        ans += revenue
    
    print("%d" % ans)

def solve(N, M, works):
    ans = 0

    return 0

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

import heapq

def ri():
    return int(input())

def rl():
    return list(input().split())

def rli():
    return list(map(int, input().split()))

def main():
    n, m = rli()
    ll = []
    for _ in range(n):
        a, b = rli()
        ll.append((a, b))
    ll.sort()
    pq = []
    l = 0
    ans = 0
    for i in range(1, m+1):
        while l < len(ll) and ll[l][0] <= i:
            heapq.heappush(pq, -ll[l][1])
            l += 1
        if len(pq) > 0:
            ans -= heapq.heappop(pq)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

from itertools import accumulate, permutations, combinations, takewhile, compress, cycle

# from functools import reduce
# from math import ceil, floor, log10, log2, factorial
# from pprint import pprint
import heapq

INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

N, M = [int(x) for x in input().split()]
AB = []
for _ in range(N):
    A, B = [int(x) for x in input().split()]
    AB.append((A, B))

AB = sorted(AB, key=lambda x: x[0])

idx = 0
available = []
ans = 0
for d in range(1, M + 1):
    while idx < N and AB[idx][0] <= d:
        heapq.heappush(available, -AB[idx][1])
        idx += 1

    if len(available) != 0:
        ans += (-heapq.heappop(available))

print(ans)

Submission status: Accepted

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

import heapq
import collections

a_all = []
for i in range(n):
    a_all.append(ab[i][0])

key_all = list(set(a_all))
key_all.sort()

d = dict()
for k in key_all:
    d[k] = []

for i in range(n):
    a = ab[i][0]
    b = ab[i][1]
    d[a].append(b)

ans = 0
l = []
for i in range(1, m+1):
    if key_all != []:
        if i == key_all[0]:
            for v in d[i]:
                heapq.heappush(l, -1 * v)

            heapq.heappop(key_all)

    if l != []:
        ans += heapq.heappop(l) * -1

print(ans)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs,heapq as hq
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0][0]
    su = [x[0]]
    for i in range(len(x)-1):
        if aa != x[i+1][0]:
            a.append(su)
            aa = x[i+1][0]
            su = [x[i+1]]
        else:
            su.append(x[i+1])
    a.append(su)
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))


n,m = l()

a = []

for i in range(n):
    z,x = l()
    a.append([z,x])

a.sort(key = lambda x:(x[0],-x[1]))
kkk = s(a)
co = 0
p = 0
al = []
for i in range(m):
    k = i + 1
    if p <= len(kkk)-1:
        if k >= kkk[p][0][0]:
            for ppp in kkk[p]:
                hq.heappush(al,-ppp[1])
            p += 1
    if len(al) != 0:
        an = hq.heappop(al)
        co -= an 
print(co)

Submission status: Accepted

Solution code:
import bisect
N,M = map(int,input().split())
C = []
for _ in range(N):
    A,B = map(int,input().split())
    C.append([A,B])
C = sorted(C,key=lambda x:x[0],reverse=True)
C = sorted(C,key=lambda x:x[1],reverse=True)
rev = 0
hist = list(range(0,M+1))
for x in C:
    A,B = x[0],x[1]
    ind = bisect.bisect_right(hist,M-A)
    if ind>0:
        hist.pop(ind-1)
        rev += B
print(rev)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
N, M = map(int, input().split())

import bisect

ABs = [[] for _ in range(M + 1)]
for i in range(N):
    A, B = map(int, input().split())
    if A <= M:
        ABs[A].append(B)
ABs[0].sort()

As = 0
for i in range(M + 1):
    if i > 0:
        for b in ABs[i]:
            bisect.insort_left(ABs[0], b)
    if len(ABs[0]) > 0:
        As += ABs[0].pop()
print(As)

Submission status: Accepted

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

import heapq

def readInts():
  return [int(s) for s in input().split(" ")]

def main():
  N, M = readInts()
  tasks = [tuple(readInts()) for _ in range(N)]
  tasks.sort()

  h = []
  cur = 0
  ans = 0
  for m in range(1, M+1):
    while cur < len(tasks) and tasks[cur][0] <= m:
      heapq.heappush(h, -1 * tasks[cur][1])
      cur += 1
    if len(h) > 0:
      ans += -1 * heapq.heappop(h)
  print(ans)

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
ABs = [0] * N
day_dic = {}

for i in range(N):
    ABs[i] = list(map(int, input().split()))

ABs = sorted(ABs, reverse=True, key=lambda x: x[1])

rewards = [0] * (M + 1)

count = 0
for AB in ABs:
    day, reward = AB
    if day <= M:
        if rewards[day] == 0:
            rewards[day] = reward
            day_dic[day] = day
            count += 1
        else:
            esti = day_dic.get(day)
            if esti is None:
                esti = day
            for i in range(esti, M + 1):
                if rewards[i] == 0:
                    rewards[i] = reward
                    day_dic[day] = i
                    count += 1
                    break
    if count == M:
        break

result = sum(rewards)
print(result)

Submission status: Accepted

Solution code:
from heapq import *

N, M = [int(i) for i in input().split()]
L = []
for _ in range(N):
    a, b = [int(i) for i in input().split()]
    L.append((a, -b))
L.sort()

Q = []
cur = 0
ans = 0
for i in range(1, M + 1):
    while cur < N:
        a, b = L[cur]
        if a > i:
            break
        heappush(Q, b)
        cur += 1
    if Q:
        ans -= heappop(Q)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import defaultdict
N, M = map(int, input().split())
d = defaultdict(list)  # {deadline: [rewards]}
for _ in range(N):
    A, B = map(int, input().split())
    deadline = M - A
    d[deadline].append(B)

ans = list()
for day in range(M + 1):
    rewards = d.get(day)
    if rewards is None or len(rewards) == 0:
        continue
    # rewards.sort(reverse=True)
    for reward in rewards:
        if len(ans) <= day:
            heappush(ans, reward)
        else:
            min_reward = heappop(ans)
            if reward > min_reward:
                heappush(ans, reward)
            else:
                heappush(ans, min_reward)

print(sum(ans))

Submission status: Accepted

Solution code:
import heapq
n,m = input().split(" ")
n = int(n)
m = int(m)

arr = [[] for _ in range(m)]

for i in range(n):
  a,b = input().split(" ")
  a = int(a)
  b = - int(b) # for heap
  
  if a > m:
    continue
    
  arr[a-1].append(b)

vs = []
heapq.heapify(vs)

res = 0
for item in arr:
  for v in item:
	  heapq.heappush(vs, v)
  
  if len(vs) == 0:
    continue
    
  maxi = heapq.heappop(vs)
  res += (-1* maxi)
  
print(res)

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect


visit = []

def aaa(ind_lim, dame_num):
    global visit
    if ind_lim >= dame_num:
        return -1
    elif visit[ind_lim] == -1:
        return -1
    elif visit[ind_lim] == 0:
        return ind_lim
    else:
        visit[ind_lim] = aaa(visit[ind_lim], dame_num)
        return visit[ind_lim]

def main():
    num, max_num = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(num)]

    data.sort(key=lambda x:(-x[1]))
    # for

    global visit
    visit = [0 for i in range(max_num + 1)]

    ans = 0

    for i in range(num):
        day, value = data[i]
        ind_lim = day
        # print(i, num, visit)
        ind_insert = aaa(ind_lim, max_num + 1)
        if ind_insert != -1:
            visit[ind_insert] = ind_insert + 1
            ans += value

    # print('uuu')
    print(ans)







if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
import sys
from collections import deque
import heapq
sys.setrecursionlimit(100000000)

def solve():
  n,m = (int(i) for i in input().split())
  query = []
  for i in range(n):
    a,b = (int(i) for i in input().split())
    query.append((a,b))
  query = sorted(query,reverse = False)
  query2 = []
  for i in range(n):
    query2 += [query[i][0]]

  ans = 0
  judge = []
  for i in range(m):
    left = bisect.bisect_left(query2,i+1)
    right = bisect.bisect_right(query2,i+1)
    for j in range(left,right):
     b,a = (query[j])
     heapq.heappush(judge, [-a,b])
    #print(judge)
    if len(judge) != 0:
     b,a = heapq.heappop(judge)
     ans += -b
  print(ans)
solve()

Submission status: Accepted

Solution code:
from operator import itemgetter
N,M = map(int,input().split())

AB = []
for i in range(N):
    Ai,Bi = map(int,input().split())
    AB.append([Ai,Bi])

AB.sort(key=itemgetter(1),reverse=True)
AB.sort(key=itemgetter(0))
from heapq import heappush, heappop
hq = []
i = 0
now = 1
ans = 0
while True:
    if i == N:
        if now <= M:
            if len(hq) == 0:
                break
            ans -= heappop(hq)
            now += 1
            continue
        else:
            break
    if AB[i][0] == now:
        heappush(hq,-AB[i][1])
        i += 1
        continue
    else:
        if now > M:
            break
        if len(hq) == 0:
            now += 1
            continue
        ans -= heappop(hq)
        now += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())

B = [tuple(map(int, input().split())) for _ in range(N)]
B.sort(reverse=True)

import heapq

hq = []
ans = 0
for i in range(1, M+1):
    while B and B[-1][0] == i:
        heapq.heappush(hq, B.pop()[1]*(-1))
    if hq:
        ans -= heapq.heappop(hq)

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

n, m = map(int, input().split(" "))
xys = [tuple(map(int, input().split(" "))) for i in range(n)]
xys = sorted(xys, key=lambda x: (x[0], -x[1]))

ans = 0

j = 0
h = []
for i in range(1, m + 1):
    while j < len(xys) and xys[j][0] <= i:
        heappush(h, -xys[j][1])
        j += 1
    if h:
        x = -heappop(h)
        # print("Pick", x)
        ans += x

print(ans)

Submission status: Accepted

Solution code:
# A, B = [int(i) for i in input().split(" ")]
# A = int(input())
# As = [int(i) for i in input().split(" ")]
# Ss = ["".join(sorted(input())) for _ in range(N)]
# from math import factorial
# def nCr(n, r):
#   return factorial(n) // factorial(r) // factorial(n - r)

import heapq
N, M = [int(i) for i in input().split(" ")]
ABs = []
for _ in range(N):
   A, B = [int(i) for i in input().split(" ")]
   ABs.append([A, B])
ABs.sort(key=lambda ab: (ab[0], -ab[1]))
ans = 0
day = 1
k = 0
pq = []
while day <= M:
  while True:
    if k < len(ABs) and ABs[k][0] <= day:
      heapq.heappush(pq, -ABs[k][1])
      k += 1
    else:
      break
  if pq:
    v = heapq.heappop(pq)
    ans += -v
  day += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
AB_dict = defaultdict(list)
AB = sorted([tuple(map(int, input().split())) for i in range(N)], reverse=True, key=lambda x: x[0])
AB = sorted(AB, reverse=True, key=lambda x: x[1])
EF = [M-i for i in range(10**5+1)]
ans = [0 for i in range(M)]
for i in range(N):
    Ai, Bi = AB[i]
    ans_i = EF[Ai]
    while ans_i >= 0 and ans[ans_i] != 0:
        ans_i -= 1
    if ans_i >= 0:
        ans[ans_i] = max(ans[ans_i], Bi)
        EF[Ai] = ans_i - 1
    else:
        EF[Ai] = ans_i
print(sum(ans))

Submission status: Accepted

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

import heapq


def g(Q, n):
    x = 0

    for i in range(n):
        if len(Q) == 0:
            break

        x += -heapq.heappop(Q)

    return x


def f(AB, M):
    lastA = None
    Q = []
    sumOfB = 0

    for a,b in AB:
        if a > M:
            break

        if a != lastA:
            if lastA != None:
                sumOfB += g(Q, a-lastA)

            lastA = a

        heapq.heappush(Q, -b)
            
    if lastA != None:
        sumOfB += g(Q, M-lastA+1)

    return sumOfB


def main():
    N,M = map(int, input().split())
    AB = sorted(list(map(int, input().split())) for i in range(N))

    print(f(AB, M))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return list(map(float, sys.stdin.readline().split()))
def LS():return sys.stdin.readline().split()
def SR(n): return [list(sys.stdin.readline())[:-1] for i in range(n)]
def IR(n): return [int(sys.stdin.readline()) for i in range(n)]
def LIR(n): return [list(map(int, sys.stdin.readline().split())) for i in range(n)]
def LSR(n): return [list(map(list, sys.stdin.readline().split())) for i in range(n)]
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
sys.setrecursionlimit(1000000)
INF = float('inf')
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N, M = LI()
AB = LIR(N)

parts = [[] for i in range(M)]
for A, B in AB:
    if (A>M):
        continue
    parts[A-1].append(B)

ans = 0

h = []


for i in range(M):
    for part in parts[i]:
        heappush(h, -part)
    if not (h):
        continue
    ans += -heappop(h)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def main():
    N, M = map( int, input().split())
    L = [(0,0) for _ in range(N)]
    for i in range(N):
        a, b = map( int, input().split())
        L[i] = (b,a)
    L.sort(reverse = True)
    V = [0]*M
    W = [ i for i in range(M)]
    def find(A,x):
        p = A[x]
        if p == x:
            return x
        a = find(A,p)
        A[x] = a
        return a
 
    def union(A, x, y):
        #    bx, by = sorted([find(A,x), find(A,y)]) # bx, by = find(A,x), find(A,y)だと無限ループ。
        if find(A,x) > find(A,y):
            bx, by = find(A,y), find(A,x)
        else:
            bx, by = find(A,x), find(A,y)
        A[y] = bx
        A[by] = bx

    for i in range(N):
        b, a = L[i]
        t = M-a
        if t < 0:
            continue
        if V[t] == 0:
            V[t] = b
            if t > 0:
                if V[t-1] > 0:
                    union(W, t, t-1)
            if t < M-1:
                if V[t+1] > 0:
                    union(W, t, t+1)
            continue
        s = find(W,t)
        if s == 0:
            if V[0] == 0:
                V[0] = b
                if M > 1:
                    if V[1] > 0:
                        union(W, 0, 1)
        else:
            V[s-1] = b
            if s-1 > 0:
                if V[s-2] > 0:
                    union(W, s-1, s-2)
            union(W,s-1,s)
    print( sum(V))
            
            
            
            
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import re
from collections import deque
import sys
import math
input = sys.stdin.readline


def int_raw():
    return int(input())


def ss_raw():
    return input().split()


def ints_raw():
    return tuple(map(int, ss_raw()))


DIV = 10**9+7


def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def ncr(n, r, mod=DIV):
	r = min(r, n-r)
	ret = 1
	for i in range(1, r+1):
		ret = ret * (n-i+1) % mod
		ret = ret * mod_inv(i, mod) % mod
	return ret


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.mini = [i for i in range(n+1)]

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
        mini = min(self.mini[x],self.mini[y])
        self.mini[x]=mini
        self.mini[y]=mini
    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

def main():
    N ,M = ints_raw()
    days = [0]*M
    uft = UnionFind(M)
    ABs = [ints_raw() for _ in range(N)]
    ABs.sort(key=lambda x:x[1],reverse=True)
    ans = 0
    for AB in ABs:
        A,B = AB
        if A > M:
            continue
        else:
            C = M-A
            par = uft.mini[uft.find(C)]

            if days[par] == 0:
                days[par]=1
                ans += B
                #uft.union(par,C)
                if par > 0:
                    uft.union(par-1,par)

            #while days[C]==1 and C>=0:
            #    C-=1
            #if C>=0:
            #    days[C]=1
            #    ans+=B
    return ans

    
print(main())