結果

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

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    M = int(input[idx+1])
    idx +=2
    
    xi0 = []
    xi1 = []
    xi2 = []
    xi3 = []
    
    for _ in range(N):
        xi = int(input[idx])
        ai = int(input[idx+1])
        bi = int(input[idx+2])
        idx +=3
        if xi == 0:
            xi0.append((ai, bi))
        elif xi == 1:
            xi1.append((ai, bi))
        elif xi == 2:
            xi2.append((ai, bi))
        elif xi == 3:
            xi3.append((ai, bi))
    
    C0 = len(xi2) + len(xi3)
    C3 = len(xi3)
    
    if C0 >= M:
        print(C3)
        return
    
    K = M - C0
    
    sorted_xi0 = sorted(xi0, key=lambda x: x[0])
    sorted_xi1 = sorted(xi1, key=lambda x: x[0])
    sorted_xi2 = sorted(xi2, key=lambda x: x[0])
    
    ai_xi0 = [x[0] for x in sorted_xi0]
    ai_xi1 = [x[0] for x in sorted_xi1]
    ai_xi2 = [x[0] for x in sorted_xi2]
    
    possible_SA = set()
    for ai, _ in xi0 + xi1 + xi2:
        possible_SA.add(ai)
    possible_SA.add(0)
    possible_SA.add(100001 + 1)
    possible_SA = sorted(possible_SA)
    
    min_three_plus = float('inf')
    
    for SA in possible_SA:
        sum_a1_xi1 = len(sorted_xi1) - bisect.bisect_left(ai_xi1, SA)
        sum_a0_xi1 = len(sorted_xi1) - sum_a1_xi1
        sum_a1_xi0 = len(sorted_xi0) - bisect.bisect_left(ai_xi0, SA)
        len_B = sum_a0_xi1 + sum_a1_xi0
        R = K - sum_a1_xi1
        
        if sum_a1_xi1 + len_B < K:
            continue
        
        if R <= 0:
            sum_xi2_a1 = len(sorted_xi2) - bisect.bisect_left(ai_xi2, SA)
            three_plus = C3 + sum_xi2_a1
            if three_plus < min_three_plus:
                min_three_plus = three_plus
            continue
        
        bi_xi1_a0 = [p[1] for p in sorted_xi1[:sum_a0_xi1]]
        bi_xi0_a1 = [p[1] for p in sorted_xi0[-sum_a1_xi0:]] if sum_a1_xi0 > 0 else []
        B_list = bi_xi1_a0 + bi_xi0_a1
        
        if len(B_list) < R:
            continue
        
        B_list_sorted = sorted(B_list)
        SB = B_list_sorted[-R]
        
        k_xi2 = bisect.bisect_left(ai_xi2, SA)
        xi2_a0 = sorted_xi2[:k_xi2]
        count_xi2_a0_ge_SB = 0
        for p in xi2_a0:
            if p[1] >= SB:
                count_xi2_a0_ge_SB += 1
        
        m_xi1 = sum_a1_xi1
        xi1_a1 = sorted_xi1[-m_xi1:] if m_xi1 > 0 else []
        count_xi1_a1_ge_SB = 0
        for p in xi1_a1:
            if p[1] >= SB:
                count_xi1_a1_ge_SB += 1
        
        sum_xi2_a1 = len(sorted_xi2) - bisect.bisect_left(ai_xi2, SA)
        three_plus = C3 + sum_xi2_a1 + count_xi2_a0_ge_SB + count_xi1_a1_ge_SB
        
        if three_plus < min_three_plus:
            min_three_plus = three_plus
    
    print(min_three_plus)

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