結果

問題 No.255 Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ
コンテスト
ユーザー lam6er
提出日時 2025-04-16 15:59:40
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,137 bytes
コンパイル時間 268 ms
コンパイル使用メモリ 81,640 KB
実行使用メモリ 299,836 KB
最終ジャッジ日時 2025-04-16 16:02:43
合計ジャッジ時間 14,123 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 MLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**18 + 9

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    ptr = 0
    N = int(data[ptr])
    ptr += 1
    Q = int(data[ptr])
    ptr += 1
    
    intervals = [(0, N, None, 0)]  # start, end (exclusive), color (0-4 for A-E), thickness
    bonus_points = [0] * 5
    
    for _ in range(Q):
        x = int(data[ptr])
        ptr += 1
        l = int(data[ptr])
        ptr += 1
        r = int(data[ptr])
        ptr += 1
        r += 1  # convert to exclusive end
        
        if x == 0:
            # Bonus query
            bonus = [0] * 5
            for start, end, color, thick in intervals:
                if color is None:
                    continue
                overlap_start = max(start, l)
                overlap_end = min(end, r)
                if overlap_start >= overlap_end:
                    continue
                team = color
                bonus[team] += (overlap_end - overlap_start) * thick
            max_b = max(bonus)
            if max_b == 0:
                continue
            count = bonus.count(max_b)
            if count == 1:
                idx = bonus.index(max_b)
                bonus_points[idx] = (bonus_points[idx] + max_b) % MOD
        else:
            # Painting operation
            team = x - 1  # 0-based (A=0, B=1, ...)
            new_intervals = []
            for start, end, color, thick in intervals:
                if end <= l or start >= r:
                    new_intervals.append((start, end, color, thick))
                    continue
                # Split into left, middle, right
                # Left part
                if start < l:
                    new_intervals.append((start, l, color, thick))
                # Middle part
                mid_start = max(start, l)
                mid_end = min(end, r)
                if mid_start < mid_end:
                    if color == team:
                        new_thick = thick + 1
                    else:
                        new_thick = 1
                    new_intervals.append((mid_start, mid_end, team, new_thick))
                # Right part
                if end > r:
                    new_intervals.append((r, end, color, thick))
            # Merge adjacent intervals
            merged = []
            for interval in new_intervals:
                if not merged:
                    merged.append(interval)
                else:
                    last = merged[-1]
                    if last[1] == interval[0] and last[2] == interval[2] and last[3] == interval[3]:
                        merged[-1] = (last[0], interval[1], last[2], last[3])
                    else:
                        merged.append(interval)
            intervals = merged
    
    # Calculate final thickness sums
    total = [0] * 5
    for start, end, color, thick in intervals:
        if color is not None:
            total[color] += (end - start) * thick
    
    # Add bonus points
    for i in range(5):
        total[i] = (total[i] + bonus_points[i]) % MOD
    
    print(' '.join(map(str, total)))
    
if __name__ == '__main__':
    main()
0