結果

問題 No.568 じゃんじゃん　落とす　委員会
ユーザー lam6er
提出日時 2025-04-16 15:44:05
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,602 bytes
コンパイル時間 370 ms
コンパイル使用メモリ 81,676 KB
実行使用メモリ 145,160 KB
最終ジャッジ日時 2025-04-16 15:47:00
合計ジャッジ時間 4,948 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

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

    participants = []
    ai_values = set()
    bi_values = set()
    C_ge2 = 0
    C_ge3 = 0
    C_x0 = 0
    C_x1 = 0
    C_x2 = 0

    for _ in range(N):
        xi = int(input[idx])
        idx += 1
        ai = int(input[idx])
        idx += 1
        bi = int(input[idx])
        idx += 1
        participants.append((xi, ai, bi))
        ai_values.add(ai)
        bi_values.add(bi)
        if xi >= 3:
            C_ge3 += 1
            C_ge2 += 1
        elif xi == 2:
            C_ge2 += 1
            C_x2 += 1
        elif xi == 1:
            C_x1 += 1
        else:
            C_x0 += 1

    ai_values.add(0)
    ai_values.add(100001)
    SA_candidates = sorted(ai_values)

    bi_values.add(0)
    bi_values.add(100001)
    SB_candidates = sorted(bi_values)

    min_count3 = float('inf')

    for SA in SA_candidates:
        B1_notA = []
        B0_A = []
        B2_notA = []
        B1_A = []
        K2_A = 0

        for xi, ai, bi in participants:
            A_ok = ai >= SA
            if xi == 1:
                if not A_ok:
                    B1_notA.append(bi)
                else:
                    B1_A.append(bi)
            elif xi == 0:
                if A_ok:
                    B0_A.append(bi)
            elif xi == 2:
                if not A_ok:
                    B2_notA.append(bi)
                else:
                    K2_A += 1

        B1_notA.sort()
        B0_A.sort()
        B2_notA.sort()
        B1_A.sort()

        K1_A = len(B1_A)
        count_2_base = (C_ge2) + K1_A

        left = 0
        right = len(SB_candidates) - 1
        best_SB = -1

        while left <= right:
            mid = (left + right) // 2
            SB = SB_candidates[mid]

            cnt_B1_notA = len(B1_notA) - bisect.bisect_left(B1_notA, SB)
            cnt_B0_A = len(B0_A) - bisect.bisect_left(B0_A, SB)
            current_count2 = count_2_base + cnt_B1_notA + cnt_B0_A

            if current_count2 >= M:
                best_SB = SB
                left = mid + 1
            else:
                right = mid - 1

        if best_SB == -1:
            continue

        cnt_B2_notA = len(B2_notA) - bisect.bisect_left(B2_notA, best_SB)
        cnt_B1_A = len(B1_A) - bisect.bisect_left(B1_A, best_SB)
        count3 = C_ge3 + K2_A + cnt_B2_notA + cnt_B1_A

        if count3 < min_count3:
            min_count3 = count3

    print(min_count3)

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