結果

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

ソースコード

diff # 

import bisect

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-1, 0, 0)]  # (start, end, team, thickness)
    bonus = [0] * 6  # 1-based indexing
    
    for _ in range(Q):
        x = int(data[ptr])
        ptr += 1
        l = int(data[ptr])
        ptr += 1
        r = int(data[ptr])
        ptr += 1
        
        if x == 0:
            # Bonus query
            sums = [0] * 6  # 0-5, but 0 is unused
            for s, e, t, th in intervals:
                overlap_start = max(s, l)
                overlap_end = min(e, r)
                if overlap_start > overlap_end:
                    continue
                length = overlap_end - overlap_start + 1
                sums[t] += th * length
            max_sum = max(sums)
            count_max = sums.count(max_sum)
            if count_max == 1:
                for i in range(1, 6):
                    if sums[i] == max_sum:
                        bonus[i] = (bonus[i] + max_sum) % MOD
                        break
        else:
            # Painting operation, team x (1-5)
            team = x
            a = l
            b = r
            
            # Split at a
            i = bisect.bisect_left(intervals, (a,)) - 1
            if i >= 0:
                s, e, t, th = intervals[i]
                if s <= a <= e:
                    # Split into [s, a-1] and [a, e]
                    intervals.pop(i)
                    intervals.insert(i, (s, a-1, t, th))
                    intervals.insert(i+1, (a, e, t, th))
            
            # Split at b+1
            split_pos = b + 1
            if split_pos <= N-1:
                i = bisect.bisect_left(intervals, (split_pos,)) - 1
                if i >= 0:
                    s, e, t, th = intervals[i]
                    if s <= split_pos <= e:
                        intervals.pop(i)
                        intervals.insert(i, (s, split_pos-1, t, th))
                        intervals.insert(i+1, (split_pos, e, t, th))
            
            # Find all intervals within [a, b]
            left = bisect.bisect_left(intervals, (a,))
            while left > 0 and intervals[left-1][1] >= a:
                left -= 1
            
            right = bisect.bisect_right(intervals, (b,))
            to_remove = []
            for i in range(left, len(intervals)):
                s, e, t, th = intervals[i]
                if s > b:
                    break
                to_remove.append(i)
            
            new_segments = []
            for i in reversed(to_remove):
                s, e, t, th = intervals.pop(i)
                new_segments.append((s, e, t, th))
            
            new_segments.reverse()
            
            for s, e, t, th in new_segments:
                new_t = team
                if t == new_t:
                    new_th = th + 1
                else:
                    new_th = 1
                # Insert the new interval
                pos = bisect.bisect_left(intervals, (s,))
                intervals.insert(pos, (s, e, new_t, new_th))
    
    # Calculate the final scores
    scores = [0] * 6  # 0-5, 0 unused
    for s, e, t, th in intervals:
        scores[t] += th * (e - s + 1)
    
    for i in range(1, 6):
        scores[i] = (scores[i] + bonus[i]) % MOD
    
    print(' '.join(map(str, scores[1:6])))

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