結果

問題 No.2422 regisys?
ユーザー gew1fw
提出日時 2025-06-12 19:22:05
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,576 bytes
コンパイル時間 223 ms
コンパイル使用メモリ 82,232 KB
実行使用メモリ 184,676 KB
最終ジャッジ日時 2025-06-12 19:22:54
合計ジャッジ時間 31,224 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 46 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

n, m = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

type0 = []
type1 = []

for _ in range(m):
    t, c = map(int, input().split())
    if t == 0:
        type0.append(c)
    else:
        type1.append(c)

type0.sort(reverse=True)
type1.sort(reverse=True)

def simulate(type0_first):
    taken = [False] * n
    if type0_first:
        # Process type0 first, items sorted by A_i
        sorted_items = sorted([(A[i], B[i], i) for i in range(n)], key=lambda x: x[0])
        ptr = len(sorted_items) - 1
        count0 = 0
        for c in type0:
            while ptr >= 0 and (sorted_items[ptr][0] > c or taken[sorted_items[ptr][2]]):
                ptr -= 1
            if ptr >= 0:
                taken[sorted_items[ptr][2]] = True
                ptr -= 1
                count0 += 1
        # Collect remaining items sorted by B_i
        remaining = []
        for a, b, idx in sorted_items:
            if not taken[idx]:
                remaining.append((b, a, idx))  # (B_i, A_i, idx)
        remaining.sort(key=lambda x: x[0])
        ptr = len(remaining) - 1
        count1 = 0
        for c in type1:
            while ptr >= 0 and (remaining[ptr][0] > c or taken[remaining[ptr][2]]):
                ptr -= 1
            if ptr >= 0:
                taken[remaining[ptr][2]] = True
                ptr -= 1
                count1 += 1
        return count0 + count1
    else:
        # Process type1 first, items sorted by B_i
        sorted_items = sorted([(B[i], A[i], i) for i in range(n)], key=lambda x: x[0])
        ptr = len(sorted_items) - 1
        count1 = 0
        for c in type1:
            while ptr >= 0 and (sorted_items[ptr][0] > c or taken[sorted_items[ptr][2]]):
                ptr -= 1
            if ptr >= 0:
                taken[sorted_items[ptr][2]] = True
                ptr -= 1
                count1 += 1
        # Collect remaining items sorted by A_i
        remaining = []
        for b, a, idx in sorted_items:
            if not taken[idx]:
                remaining.append((a, b, idx))  # (A_i, B_i, idx)
        remaining.sort(key=lambda x: x[0])
        ptr = len(remaining) - 1
        count0 = 0
        for c in type0:
            while ptr >= 0 and (remaining[ptr][0] > c or taken[remaining[ptr][2]]):
                ptr -= 1
            if ptr >= 0:
                taken[remaining[ptr][2]] = True
                ptr -= 1
                count0 += 1
        return count0 + count1

total1 = simulate(True)
total2 = simulate(False)

print(n - max(total1, total2))
0