結果

問題 No.568 じゃんじゃん　落とす　委員会
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:50:11
言語 PyPy3
(7.3.17)
結果
WA  
実行時間 -
コード長 4,613 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 261 ms
コンパイル使用メモリ 82,384 KB
実行使用メモリ 276,728 KB
最終ジャッジ日時 2025-03-31 17:51:09
合計ジャッジ時間 5,336 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6 WA * 7 TLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import bisect

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.size = 1
        while self.size < self.n:
            self.size <<= 1
        self.tree = [[] for _ in range(2 * self.size)]
        for i in range(self.n):
            self.tree[self.size + i] = [data[i]]
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = sorted(self.tree[2 * i] + self.tree[2 * i + 1])
    
    def query_ge_count(self, l, r, x):
        res = 0
        l += self.size
        r += self.size
        while l <= r:
            if l % 2 == 1:
                pos = bisect.bisect_left(self.tree[l], x)
                res += len(self.tree[l]) - pos
                l += 1
            if r % 2 == 0:
                pos = bisect.bisect_left(self.tree[r], x)
                res += len(self.tree[r]) - pos
                r -= 1
            l >>= 1
            r >>= 1
        return res

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    n, m = int(data[idx]), int(data[idx+1])
    idx +=2
    
    xi3 = 0
    xi2_group = []
    xi1_group = []
    xi0_group = []
    for _ in range(n):
        xi, ai, bi = int(data[idx]), int(data[idx+1]), int(data[idx+2])
        idx +=3
        if xi >=3:
            xi3 +=1
        elif xi ==2:
            xi2_group.append( (ai, bi) )
        elif xi ==1:
            xi1_group.append( (ai, bi) )
        else:
            xi0_group.append( (ai, bi) )
    
    count_xi3 = xi3
    count_xi2 = len(xi2_group)
    
    def process_group(group):
        group.sort(key=lambda x: x[0])
        sorted_ai = [x[0] for x in group]
        sorted_bi = [x[1] for x in group]
        if group:
            st = SegmentTree( [x[1] for x in group] )
        else:
            st = None
        return sorted_ai, sorted_bi, st
    
    sorted_ai_xi0, sorted_bi_xi0, st_xi0 = process_group(xi0_group)
    sorted_ai_xi1, sorted_bi_xi1, st_xi1 = process_group(xi1_group)
    sorted_ai_xi2, sorted_bi_xi2, st_xi2 = process_group(xi2_group)
    
    sa_candidates = set()
    for ai, _ in xi0_group:
        sa_candidates.add(ai)
    for ai, _ in xi1_group:
        sa_candidates.add(ai)
    for ai, _ in xi2_group:
        sa_candidates.add(ai)
    sa_candidates.add(0)
    sa_candidates.add(100001 + 1)
    sa_list = sorted(sa_candidates)
    
    best = float('inf')
    
    len_xi0 = len(xi0_group)
    len_xi1 = len(xi1_group)
    len_xi2 = len(xi2_group)
    
    for sa in sa_list:
        idx_xi1 = bisect.bisect_left(sorted_ai_xi1, sa)
        count_xi1_ge = len_xi1 - idx_xi1
        
        required = m - (count_xi3 + count_xi2 + count_xi1_ge)
        if required <0:
            required =0
        
        if required <=0:
            idx_xi2 = bisect.bisect_left(sorted_ai_xi2, sa)
            A_xi2_SA = len_xi2 - idx_xi2
            current = count_xi3 + A_xi2_SA
            if current < best:
                best = current
            continue
        
        l = 0
        h = 100001 +1
        best_sb = -1
        
        len_xi0_ge = len_xi0 - bisect.bisect_left(sorted_ai_xi0, sa)
        if len_xi0_ge >0:
            start_xi0_ge = bisect.bisect_left(sorted_ai_xi0, sa)
            sorted_bi_xi0_ge = sorted_bi_xi0[start_xi0_ge:]
        else:
            sorted_bi_xi0_ge = []
        
        while l <=h:
            mid = (l + h)//2
            sum1 =0
            if st_xi1 and idx_xi1 >0:
                sum1 = st_xi1.query_ge_count(0, idx_xi1-1, mid)
            sum2 =0
            if sorted_bi_xi0_ge:
                pos = bisect.bisect_left(sorted_bi_xi0_ge, mid)
                sum2 = len(sorted_bi_xi0_ge) - pos
            total = sum1 + sum2
            if total >= required:
                best_sb = mid
                l = mid +1
            else:
                h = mid -1
        
        if best_sb == -1:
            continue
        
        sum3 =0
        idx_xi2 = bisect.bisect_left(sorted_ai_xi2, sa)
        if st_xi2 and idx_xi2 >0:
            sum3 = st_xi2.query_ge_count(0, idx_xi2-1, best_sb)
        
        sum4 =0
        if len_xi1 >0 and idx_xi1 < len_xi1:
            start = idx_xi1
            end = len_xi1 -1
            len_ge = end - start +1
            sorted_bi_xi1_ge = sorted_bi_xi1[start:]
            pos = bisect.bisect_left(sorted_bi_xi1_ge, best_sb)
            sum4 = len(sorted_bi_xi1_ge) - pos
        
        A_xi2_SA = len_xi2 - idx_xi2
        current = count_xi3 + A_xi2_SA + sum3 + sum4
        if current < best:
            best = current
    
    print(best)

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