結果

問題 No.568 じゃんじゃん　落とす　委員会
コンテスト
ユーザー lam6er
提出日時 2025-04-15 21:56:03
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,574 bytes
コンパイル時間 337 ms
コンパイル使用メモリ 82,180 KB
実行使用メモリ 126,452 KB
最終ジャッジ日時 2025-04-15 21:57:44
合計ジャッジ時間 5,129 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 13 TLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    M = int(input[ptr])
    ptr += 1

    xi3 = []
    xi2 = []
    xi1 = []
    xi0 = []

    for _ in range(N):
        xi = int(input[ptr])
        ptr += 1
        ai = int(input[ptr])
        ptr += 1
        bi = int(input[ptr])
        ptr += 1
        if xi == 3:
            xi3.append((ai, bi))
        elif xi == 2:
            xi2.append((ai, bi))
        elif xi == 1:
            xi1.append((ai, bi))
        else:
            xi0.append((ai, bi))

    xi2.sort()
    xi1.sort()
    xi0.sort()

    SA_candidates = set()
    for ai, bi in xi2:
        SA_candidates.add(ai)
    for ai, bi in xi1:
        SA_candidates.add(ai)
    for ai, bi in xi0:
        SA_candidates.add(ai)
    SA_candidates.add(100001)
    SA_candidates = sorted(SA_candidates)

    min_three = float('inf')

    xi2_ai = [ai for ai, bi in xi2]
    xi1_ai = [ai for ai, bi in xi1]
    xi0_ai = [ai for ai, bi in xi0]

    for SA in SA_candidates:
        type1 = len(xi3)

        type2 = len(xi2) - bisect.bisect_left(xi2_ai, SA)
        type3 = len(xi2) - type2

        type4 = len(xi1) - bisect.bisect_left(xi1_ai, SA)
        type5 = len(xi1) - type4

        type6 = len(xi0) - bisect.bisect_left(xi0_ai, SA)
        type7 = len(xi0) - type6

        fixed_2 = type1 + type2 + type3 + type4

        if fixed_2 >= M:
            three_plus = type1 + type2
            if three_plus < min_three:
                min_three = three_plus
            continue

        required = M - fixed_2
        if required <= 0:
            three_plus = type1 + type2
            if three_plus < min_three:
                min_three = three_plus
            continue

        type5_B = []
        pos = bisect.bisect_left(xi1_ai, SA)
        for i in range(pos):
            type5_B.append(xi1[i][1])

        type6_B = []
        pos = bisect.bisect_left(xi0_ai, SA)
        for i in range(pos, len(xi0)):
            type6_B.append(xi0[i][1])

        B_list = type5_B + type6_B
        if len(B_list) < required:
            continue

        B_list.sort()
        SB = B_list[-required]

        count = 0
        for ai, bi in xi2:
            if ai < SA and bi >= SB:
                count += 1

        for ai, bi in xi1:
            if ai >= SA and bi >= SB:
                count += 1

        three_plus = type1 + type2 + count
        if three_plus < min_three:
            min_three = three_plus

    print(min_three)

if __name__ == "__main__":
    main()
0