結果

問題 No.255 Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ
ユーザー gew1fw
提出日時 2025-06-12 13:01:27
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,550 bytes
コンパイル時間 230 ms
コンパイル使用メモリ 82,316 KB
実行使用メモリ 280,684 KB
最終ジャッジ日時 2025-06-12 13:07:51
合計ジャッジ時間 15,237 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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

    intervals = [(0, N, 0, 0)]  # (start, end, color, thickness), color 0 is unpainted
    bonus = [0] * 5  # A, B, C, D, E

    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:
            # Bonus query [l, r]
            L = l
            R = r + 1
            sums = [0] * 5
            for s, e, c, t in intervals:
                if e <= L or s >= R:
                    continue
                a = max(s, L)
                b = min(e, R)
                if a >= b:
                    continue
                if c != 0:
                    sums[c-1] += (b - a) * t
            max_sum = max(sums)
            count = 0
            for s in sums:
                if s == max_sum:
                    count += 1
            if count == 1:
                for i in range(5):
                    if sums[i] == max_sum:
                        bonus[i] = (bonus[i] + max_sum) % MOD
                        break
        else:
            # Paint operation, team X (1-5) paints [l, r]
            X = x  # team 1-5
            L_paint = l
            R_paint = r + 1  # convert to [L_paint, R_paint)
            new_intervals = []
            overlapping = []

            # Split intervals into overlapping and non-overlapping parts
            for interval in intervals:
                s, e, c, t = interval
                if e <= L_paint or s >= R_paint:
                    new_intervals.append(interval)
                else:
                    overlapping.append(interval)

            # Process overlapping intervals
            new_middles = []
            for s, e, c, t in overlapping:
                # Left part
                if s < L_paint:
                    new_intervals.append((s, L_paint, c, t))
                # Middle part
                a = max(s, L_paint)
                b = min(e, R_paint)
                if a < b:
                    if c == X:
                        new_t = t + 1
                    else:
                        new_t = 1
                    new_middles.append((a, b, X, new_t))
                # Right part
                if e > R_paint:
                    new_intervals.append((R_paint, e, c, t))

            # Merge new_middles
            if new_middles:
                # Sort by start
                new_middles.sort()
                merged = []
                current = new_middles[0]
                for interval in new_middles[1:]:
                    if interval[0] == current[1] and interval[2] == current[2] and interval[3] == current[3]:
                        current = (current[0], interval[1], current[2], current[3])
                    else:
                        merged.append(current)
                        current = interval
                merged.append(current)
                new_intervals.extend(merged)

            # Sort intervals by start
            new_intervals.sort(key=lambda x: x[0])
            intervals[:] = new_intervals

    # Calculate final scores
    total = [0] * 5
    for s, e, c, t in intervals:
        if c != 0:
            total[c-1] = (total[c-1] + (e - s) * t) % MOD

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

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

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