結果

問題 No.255 Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ
コンテスト
ユーザー lam6er
提出日時 2025-04-15 22:44:42
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,629 bytes
コンパイル時間 308 ms
コンパイル使用メモリ 81,960 KB
実行使用メモリ 316,552 KB
最終ジャッジ日時 2025-04-15 22:46:25
合計ジャッジ時間 23,247 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, None, 0)]  # start, end (exclusive), team (0-4 or None), count
    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
        r += 1  # Convert to exclusive end
        
        if x == 0:
            # Bonus query
            sum_counts = [0] * 5
            for (start, end, team, count) in intervals:
                overlap_start = max(start, l)
                overlap_end = min(end, r)
                if overlap_start >= overlap_end:
                    continue
                if team is not None:
                    sum_counts[team] += (overlap_end - overlap_start) * count
            max_sum = max(sum_counts)
            count_max = sum_counts.count(max_sum)
            if count_max == 1:
                team_idx = sum_counts.index(max_sum)
                bonus[team_idx] += max_sum
                bonus[team_idx] %= MOD
        else:
            # Painting operation
            team = x - 1  # 0-based
            new_intervals = []
            for (start, end, curr_team, curr_count) in intervals:
                if end <= l or start >= r:
                    new_intervals.append((start, end, curr_team, curr_count))
                    continue
                # Split into left, middle, right
                # Left part
                if start < l:
                    new_intervals.append((start, l, curr_team, curr_count))
                # Middle part
                mid_start = max(start, l)
                mid_end = min(end, r)
                if mid_start < mid_end:
                    if curr_team == team:
                        new_count = curr_count + 1
                    else:
                        new_count = 1
                    new_intervals.append((mid_start, mid_end, team, new_count))
                # Right part
                if end > r:
                    new_intervals.append((r, end, curr_team, curr_count))
            intervals = new_intervals
    
    # Calculate final thickness
    thickness = [0] * 5
    for (start, end, team, count) in intervals:
        if team is not None:
            thickness[team] += (end - start) * count
            thickness[team] %= MOD
    
    # Add bonus and mod
    result = [(thickness[i] + bonus[i]) % MOD for i in range(5)]
    print(' '.join(map(str, result)))

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