結果

問題 No.568 じゃんじゃん　落とす　委員会
コンテスト
ユーザー lam6er
提出日時 2025-04-15 21:54:57
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 577 ms / 1,000 ms
コード長 3,923 bytes
コンパイル時間 334 ms
コンパイル使用メモリ 81,856 KB
実行使用メモリ 144,320 KB
最終ジャッジ日時 2025-04-15 21:56:48
合計ジャッジ時間 8,074 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

class FenwickTree:
    def __init__(self, size):
        self.n = size
        self.tree = [0] * (self.n + 2)  # 1-based indexing

    def update(self, idx, delta):
        while idx <= self.n:
            self.tree[idx] += delta
            idx += idx & -idx

    def query(self, idx):
        res = 0
        while idx > 0:
            res += self.tree[idx]
            idx -= idx & -idx
        return res

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

    participants = []
    bi_values = set()

    for _ in range(N):
        xi = int(input[ptr])
        ptr += 1
        ai = int(input[ptr])
        ptr += 1
        bi = int(input[ptr])
        ptr += 1
        participants.append((xi, ai, bi))
        bi_values.add(bi)

    # Coordinate compression for Bi
    bi_list = sorted(bi_values)
    compressed = {bi: i+1 for i, bi in enumerate(bi_list)}  # 1-based
    max_bi_compressed = len(bi_list)

    # Prepare events (Ai + 1)
    events_dict = defaultdict(list)
    for idx, (xi, ai, bi) in enumerate(participants):
        ai_plus_1 = ai + 1
        events_dict[ai_plus_1].append(idx)

    sorted_events = sorted(events_dict.keys())
    sorted_events.append(100001 + 2)  # Add dummy event to process the last interval

    # Initialize Fenwick Trees for B1 and B2
    B1_tree = FenwickTree(max_bi_compressed)
    B2_tree = FenwickTree(max_bi_compressed)

    c0 = 0
    d0 = 0

    # Initial setup for a=1 scenario
    for idx, (xi, ai, bi) in enumerate(participants):
        a1_current = xi + 1
        if a1_current >= 2:
            c0 += 1
        if a1_current >= 3:
            d0 += 1
        if a1_current == 1:
            B1_tree.update(compressed[bi], 1)
        elif a1_current == 2:
            B2_tree.update(compressed[bi], 1)

    global_min = float('inf')
    prev_SA = 0

    for event_SA in sorted_events:
        # Process the interval [prev_SA, event_SA)
        K = max(0, M - c0)
        current_min = None

        if K <= 0:
            current_min = d0
        else:
            B1_size = B1_tree.query(max_bi_compressed)
            if B1_size < K:
                pass
            else:
                low = 1
                high = max_bi_compressed
                S_opt = 0
                while low <= high:
                    mid = (low + high) // 2
                    cnt = B1_tree.query(max_bi_compressed) - B1_tree.query(mid - 1)
                    if cnt >= K:
                        S_opt = mid
                        low = mid + 1
                    else:
                        high = mid - 1
                if S_opt != 0:
                    count_B2 = B2_tree.query(max_bi_compressed) - B2_tree.query(S_opt - 1)
                    current_min = d0 + count_B2

        if current_min is not None:
            if current_min < global_min:
                global_min = current_min

        # Process the event: switch participants from a=1 to a=0
        for idx in events_dict.get(event_SA, []):
            xi, ai, bi = participants[idx]
            # Remove a=1 contributions
            a1_current = xi + 1
            if a1_current >= 2:
                c0 -= 1
            if a1_current >= 3:
                d0 -= 1
            if a1_current == 1:
                B1_tree.update(compressed[bi], -1)
            elif a1_current == 2:
                B2_tree.update(compressed[bi], -1)

            # Add a=0 contributions
            a0_current = xi
            if a0_current >= 2:
                c0 += 1
            if a0_current >= 3:
                d0 += 1
            if a0_current == 1:
                B1_tree.update(compressed[bi], 1)
            elif a0_current == 2:
                B2_tree.update(compressed[bi], 1)

        prev_SA = event_SA

    print(global_min)

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