結果

問題 No.255 Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 12:55:03
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,039 bytes
コンパイル時間 433 ms
コンパイル使用メモリ 82,172 KB
実行使用メモリ 310,604 KB
最終ジャッジ日時 2025-06-12 13:00:09
合計ジャッジ時間 23,046 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other MLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**18 + 9

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

    intervals = [(0, N-1, None, 0)]
    bonus = [0] * 5

    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:
            scores = [0] * 5
            for s, e, t, c in intervals:
                if e < l or s > r:
                    continue
                start = max(s, l)
                end = min(e, r)
                if start > end:
                    continue
                if t is not None:
                    scores[t] += (end - start + 1) * c
            max_score = max(scores)
            count = 0
            idx = -1
            for i in range(5):
                if scores[i] == max_score:
                    count += 1
                    idx = i
            if count == 1:
                bonus[idx] += max_score
        else:
            team = x - 1
            new_intervals = []
            for s, e, t, c in intervals:
                if e < l or s > r:
                    new_intervals.append((s, e, t, c))
                    continue
                if s < l:
                    new_intervals.append((s, l-1, t, c))
                new_s = max(s, l)
                new_e = min(e, r)
                if new_s <= new_e:
                    if t == team:
                        new_c = c + 1
                    else:
                        new_c = 1
                    new_intervals.append((new_s, new_e, team, new_c))
                if e > r:
                    new_intervals.append((r+1, e, t, c))
            intervals = new_intervals

    total = [0] * 5
    for s, e, t, c in intervals:
        if t is not None:
            total[t] += (e - s + 1) * c

    for i in range(5):
        total[i] = (total[i] + bonus[i]) % MOD

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

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