結果

問題 No.2422 regisys?
ユーザー 👑 SPD_9X2SPD_9X2
提出日時 2023-08-23 08:01:50
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,616 ms / 2,000 ms
コード長 1,346 bytes
コンパイル時間 928 ms
コンパイル使用メモリ 86,968 KB
実行使用メモリ 150,504 KB
最終ジャッジ日時 2023-08-23 08:02:28
合計ジャッジ時間 34,369 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 76 ms
71,372 KB
testcase_01 AC 85 ms
71,152 KB
testcase_02 AC 76 ms
71,212 KB
testcase_03 AC 75 ms
71,244 KB
testcase_04 AC 77 ms
71,244 KB
testcase_05 AC 76 ms
71,288 KB
testcase_06 AC 78 ms
71,424 KB
testcase_07 AC 76 ms
71,300 KB
testcase_08 AC 78 ms
71,212 KB
testcase_09 AC 77 ms
71,448 KB
testcase_10 AC 76 ms
71,252 KB
testcase_11 AC 77 ms
71,144 KB
testcase_12 AC 75 ms
70,956 KB
testcase_13 AC 85 ms
71,108 KB
testcase_14 AC 75 ms
71,140 KB
testcase_15 AC 77 ms
71,356 KB
testcase_16 AC 78 ms
71,288 KB
testcase_17 AC 75 ms
71,376 KB
testcase_18 AC 74 ms
71,436 KB
testcase_19 AC 78 ms
71,304 KB
testcase_20 AC 77 ms
71,104 KB
testcase_21 AC 76 ms
71,148 KB
testcase_22 AC 76 ms
71,320 KB
testcase_23 AC 76 ms
71,140 KB
testcase_24 AC 76 ms
71,280 KB
testcase_25 AC 82 ms
71,100 KB
testcase_26 AC 74 ms
71,236 KB
testcase_27 AC 74 ms
71,240 KB
testcase_28 AC 76 ms
71,288 KB
testcase_29 AC 75 ms
71,140 KB
testcase_30 AC 74 ms
71,144 KB
testcase_31 AC 635 ms
104,872 KB
testcase_32 AC 630 ms
104,088 KB
testcase_33 AC 553 ms
105,328 KB
testcase_34 AC 290 ms
85,448 KB
testcase_35 AC 658 ms
109,588 KB
testcase_36 AC 449 ms
92,640 KB
testcase_37 AC 639 ms
106,784 KB
testcase_38 AC 322 ms
87,988 KB
testcase_39 AC 280 ms
85,580 KB
testcase_40 AC 396 ms
91,776 KB
testcase_41 AC 352 ms
89,696 KB
testcase_42 AC 1,167 ms
137,160 KB
testcase_43 AC 643 ms
100,920 KB
testcase_44 AC 1,188 ms
138,732 KB
testcase_45 AC 1,063 ms
130,464 KB
testcase_46 AC 1,185 ms
138,200 KB
testcase_47 AC 780 ms
105,880 KB
testcase_48 AC 1,329 ms
150,504 KB
testcase_49 AC 946 ms
114,004 KB
testcase_50 AC 1,278 ms
147,976 KB
testcase_51 AC 1,351 ms
136,380 KB
testcase_52 AC 596 ms
106,180 KB
testcase_53 AC 1,190 ms
133,568 KB
testcase_54 AC 1,344 ms
146,992 KB
testcase_55 AC 1,242 ms
136,100 KB
testcase_56 AC 711 ms
110,520 KB
testcase_57 AC 1,616 ms
149,628 KB
testcase_58 AC 1,606 ms
149,324 KB
testcase_59 AC 1,573 ms
149,480 KB
testcase_60 AC 1,564 ms
150,376 KB
testcase_61 AC 74 ms
71,164 KB
権限があれば一括ダウンロードができます

ソースコード

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