結果

問題 No.2422 regisys?
ユーザー SPD_9X2
提出日時 2023-08-23 08:01:50
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,567 ms / 2,000 ms
コード長 1,346 bytes
コンパイル時間 192 ms
コンパイル使用メモリ 82,312 KB
実行使用メモリ 146,100 KB
最終ジャッジ日時 2024-12-21 09:05:29
合計ジャッジ時間 29,691 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 61
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""

とりあえず、小さい方から見る
すると、自分が買わなかったものは後の人が買えるので、どれを選んでもOK
後は、相手側の一番高い物を買えばよい…？

"""

import sys
from sys import stdin
import heapq

N,M = map(int,stdin.readline().split())
A = list(map(int,stdin.readline().split()))
B = list(map(int,stdin.readline().split()))
CT = []

MMM = 10**10

for i in range(M):
    T,C = map(int,stdin.readline().split())
    CT.append( C*MMM+T )
CT.sort()

able = [True] * N

AtoB = [(A[i],B[i],i) for i in range(N)]
AtoB.sort(); AtoB.reverse()

BtoA = [(B[i],A[i],i) for i in range(N)]
BtoA.sort(); BtoA.reverse()

q0 = []
q1 = []

ans = N

for tmp in CT:

    C = tmp // MMM
    T = tmp % MMM

    if T == 0:
        while AtoB and AtoB[-1][0] <= C:
            na,nb,i = AtoB.pop()
            heapq.heappush( q0 , (-nb,i) )

        while q0:
            mnb,i = heapq.heappop(q0)
            if able[i]:
                able[i] = False
                ans -= 1
                break

    else:
        while BtoA and BtoA[-1][0] <= C:
            nb,na,i = BtoA.pop()
            heapq.heappush( q1, (-na,i) )

        while q1:
            mna,i = heapq.heappop(q1)
            if able[i]:
                able[i] = False
                ans -= 1
                break

print (ans)
0