結果

問題 No.255 Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 12:53:59
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 4,674 bytes
コンパイル時間 448 ms
コンパイル使用メモリ 82,292 KB
実行使用メモリ 286,804 KB
最終ジャッジ日時 2025-06-12 12:57:37
合計ジャッジ時間 15,313 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 MLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

MOD = 10**18 + 9

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

    teams = {1: [], 2: [], 3: [], 4: [], 5: []}
    bonus = {1: 0, 2: 0, 3: 0, 4: 0, 5: 0}

    for _ in range(Q):
        x = int(input[ptr])
        ptr += 1
        l = int(input[ptr])
        ptr += 1
        r = int(input[ptr])
        ptr += 1

        if x == 0:
            sum_counts = {1: 0, 2: 0, 3: 0, 4: 0, 5: 0}
            for team in teams:
                for interval in teams[team]:
                    s, e, cnt = interval
                    overlap_s = max(s, l)
                    overlap_e = min(e, r)
                    if overlap_s > overlap_e:
                        continue
                    sum_counts[team] += (overlap_e - overlap_s + 1) * cnt
            max_sum = max(sum_counts.values())
            candidates = [k for k, v in sum_counts.items() if v == max_sum]
            if len(candidates) == 1:
                bonus[candidates[0]] += max_sum
        else:
            X = x
            L = l
            R = r

            for Y in teams:
                if Y == X:
                    continue
                new_intervals = []
                for interval in teams[Y]:
                    s, e, cnt = interval
                    if e < L or s > R:
                        new_intervals.append((s, e, cnt))
                        continue
                    if s <= L - 1:
                        new_intervals.append((s, L - 1, cnt))
                    if R + 1 <= e:
                        new_intervals.append((R + 1, e, cnt))
                teams[Y] = new_intervals

            new_X_intervals = []
            to_increment = []
            for interval in teams[X]:
                s, e, cnt = interval
                if e < L or s > R:
                    new_X_intervals.append((s, e, cnt))
                    continue
                if s <= L - 1:
                    new_X_intervals.append((s, L - 1, cnt))
                part_s = max(s, L)
                part_e = min(e, R)
                if part_s <= part_e:
                    to_increment.append((part_s, part_e, cnt + 1))
                if R + 1 <= e:
                    new_X_intervals.append((R + 1, e, cnt))

            merged_to_increment = []
            for s, e, cnt in sorted(to_increment, key=lambda x: x[0]):
                if not merged_to_increment:
                    merged_to_increment.append((s, e, cnt))
                else:
                    last_s, last_e, last_cnt = merged_to_increment[-1]
                    if last_e >= s - 1 and last_cnt == cnt:
                        merged_to_increment[-1] = (last_s, max(last_e, e), cnt)
                    else:
                        merged_to_increment.append((s, e, cnt))

            current = L
            uncovered = []
            for s, e, cnt in merged_to_increment:
                if s > current:
                    uncovered.append((current, s - 1))
                current = max(current, e + 1)
            if current <= R:
                uncovered.append((current, R))

            new_uncovered = [(s, e, 1) for s, e in uncovered]
            merged = merged_to_increment + new_uncovered
            merged.sort(key=lambda x: x[0])

            final_merged = []
            for s, e, cnt in merged:
                if not final_merged:
                    final_merged.append((s, e, cnt))
                else:
                    last_s, last_e, last_cnt = final_merged[-1]
                    if last_e == s - 1 and last_cnt == cnt:
                        final_merged[-1] = (last_s, e, cnt)
                    else:
                        final_merged.append((s, e, cnt))

            combined = new_X_intervals + final_merged
            combined.sort(key=lambda x: x[0])

            merged_combined = []
            for s, e, cnt in combined:
                if not merged_combined:
                    merged_combined.append((s, e, cnt))
                else:
                    last_s, last_e, last_cnt = merged_combined[-1]
                    if last_e == s - 1 and last_cnt == cnt:
                        merged_combined[-1] = (last_s, e, cnt)
                    else:
                        merged_combined.append((s, e, cnt))
            teams[X] = merged_combined

    scores = [0] * 5
    for team in teams:
        total = 0
        for interval in teams[team]:
            s, e, cnt = interval
            total += (e - s + 1) * cnt
        scores[team - 1] = (total + bonus[team]) % MOD

    print(' '.join(map(str, scores)))

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