結果

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

ソースコード

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, -1, 0)]  # (start, end, team, thickness)
    sum_team = [0] * 5  # A-E are 0-4
    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:
            current_sum = [0] * 5
            for (s, e, t, thk) in intervals:
                if e < l or s > r:
                    continue
                os = max(s, l)
                oe = min(e, r)
                length = oe - os + 1
                if t != -1:
                    current_sum[t] += thk * length
            max_val = max(current_sum)
            count = current_sum.count(max_val)
            if count == 1:
                for i in range(5):
                    if current_sum[i] == max_val:
                        bonus[i] = (bonus[i] + max_val) % MOD
                        break
        else:
            team = x - 1  # 0-based
            new_intervals = []
            overlap_intervals = []
            non_overlap = []
            for interval in intervals:
                s, e, t, thk = interval
                if e < l or s > r:
                    non_overlap.append(interval)
                else:
                    overlap_intervals.append(interval)
            new_intervals = non_overlap.copy()
            
            for interval in overlap_intervals:
                s, e, t, thk = interval
                left = None
                if s < l:
                    left = (s, l-1, t, thk)
                right = None
                if e > r:
                    right = (r+1, e, t, thk)
                os = max(s, l)
                oe = min(e, r)
                if os > oe:
                    if left:
                        new_intervals.append(left)
                    if right:
                        new_intervals.append(right)
                    continue
                if t != -1:
                    sum_team[t] = (sum_team[t] - thk * (oe - os + 1)) % MOD
                new_t = team
                new_thk = thk + 1 if t == team else 1
                sum_team[new_t] = (sum_team[new_t] + new_thk * (oe - os + 1)) % MOD
                if left:
                    new_intervals.append(left)
                if right:
                    new_intervals.append(right)
                new_intervals.append((os, oe, new_t, new_thk))
            
            intervals = []
            if new_intervals:
                new_intervals.sort(key=lambda x: x[0])
                intervals.append(new_intervals[0])
                for i in range(1, len(new_intervals)):
                    last = intervals[-1]
                    curr = new_intervals[i]
                    if last[1] + 1 >= curr[0] and last[2] == curr[2] and last[3] == curr[3]:
                        merged = (last[0], curr[1], last[2], last[3])
                        intervals[-1] = merged
                    else:
                        intervals.append(curr)
    
    total = [ (sum_team[i] + bonus[i]) % MOD for i in range(5) ]
    print(' '.join(map(str, total)))

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