結果

問題 No.255 Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ
ユーザー lam6er
提出日時 2025-03-31 17:57:01
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,078 bytes
コンパイル時間 212 ms
コンパイル使用メモリ 82,636 KB
実行使用メモリ 137,212 KB
最終ジャッジ日時 2025-03-31 17:58:27
合計ジャッジ時間 19,431 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 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

    # Initialize the intervals
    intervals = []
    if N > 0:
        intervals = [(0, N-1, 0, 0)]  # (start, end, team, thickness)

    bonus = [0] * 5  # A-E are 0-4 in bonus array

    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
            sums = [0] * 5  # A-E
            for (a, b, team, thick) in intervals:
                if team == 0:
                    continue  # team 0 (unpainted) contributes nothing
                start = max(a, l)
                end = min(b, r)
                if start > end:
                    continue
                length = end - start + 1
                sums[team-1] += thick * length  # team 1 (A) is index 0 in sums
            max_sum = max(sums) if sums else 0
            count = sums.count(max_sum)
            if count == 1:
                idx = sums.index(max_sum)
                bonus[idx] += max_sum
                bonus[idx] %= MOD
        else:
            # Paint operation, teams are 1-5 (A-E)
            T = x
            # Process intervals
            new_intervals = []
            overlap = []
            i = 0
            # Collect overlapping intervals
            while i < len(intervals):
                a_curr, b_curr, t_curr, th_curr = intervals[i]
                if b_curr < l or a_curr > r:
                    new_intervals.append(intervals[i])
                    i += 1
                    continue
                # Overlap, collect
                overlap.append(intervals[i])
                i += 1
            # Process overlap
            for a, b, t_old, th_old in overlap:
                # Split into left, middle, right
                left = None
                if a < l:
                    left = (a, l-1, t_old, th_old)
                # Middle part
                mid_a = max(a, l)
                mid_b = min(b, r)
                if T == t_old:
                    new_th = th_old + 1
                else:
                    new_th = 1
                middle = (mid_a, mid_b, T, new_th)
                right = None
                if b > r:
                    right = (r+1, b, t_old, th_old)
                # Add left, middle, right (if exist)
                if left:
                    new_intervals.append(left)
                new_intervals.append(middle)
                if right:
                    new_intervals.append(right)
            # The non-overlapping intervals have already been added
            # Now merge new_intervals
            if not new_intervals:
                intervals = []
            else:
                # Sort by start
                new_intervals.sort()
                merged = []
                current = list(new_intervals[0])
                for interval in new_intervals[1:]:
                    a_curr, b_curr = current[0], current[1]
                    t_curr, th_curr = current[2], current[3]
                    a_new, b_new, t_new, th_new = interval
                    if (t_curr == t_new and th_curr == th_new and
                        b_curr + 1 == a_new):
                        # Merge
                        current[1] = b_new
                    else:
                        merged.append(tuple(current))
                        current = list(interval)
                merged.append(tuple(current))
                intervals = merged

    # Calculate final base scores
    base = [0] * 5
    for (a, b, team, thick) in intervals:
        if team == 0:
            continue
        length = b - a + 1
        base[team-1] += thick * length
        base[team-1] %= MOD

    # Sum base and bonus
    scores = []
    for i in range(5):
        total = (base[i] + bonus[i]) % MOD
        scores.append(total)
    print(' '.join(map(str, scores)))

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