結果

問題 No.255 Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ
ユーザー gew1fw
提出日時 2025-06-12 18:06:23
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 4,496 bytes
コンパイル時間 181 ms
コンパイル使用メモリ 83,032 KB
実行使用メモリ 299,228 KB
最終ジャッジ日時 2025-06-12 18:08:09
合計ジャッジ時間 14,658 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 MLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

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, 0, 0)]  # (start, end, team, thickness)
    bonuses = [0] * 6  # A to E are 1-5, index 0 unused

    def split(x):
        nonlocal intervals
        left = bisect.bisect_left(intervals, (x, -1, -1, -1)) - 1
        if left < 0:
            left = 0
        found = -1
        for i in range(left, len(intervals)):
            s, e, t, th = intervals[i]
            if s <= x <= e:
                found = i
                break
        if found == -1:
            return
        s, e, t, th = intervals[found]
        if s == x or e < x:
            return
        new1 = (s, x-1, t, th)
        new2 = (x, e, t, th)
        intervals.pop(found)
        intervals.insert(found, new1)
        intervals.insert(found+1, new2)

    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:
            sums = [0] * 6
            L = l
            R = r
            i = 0
            while i < len(intervals):
                s, e, t, th = intervals[i]
                if e < L:
                    i += 1
                    continue
                if s > R:
                    break
                # overlap
                a = max(s, L)
                b = min(e, R)
                if a > b:
                    i += 1
                    continue
                sums[t] += (b - a + 1) * th
                i += 1
            max_sum = max(sums)
            count = 0
            team = -1
            for idx in range(6):
                if sums[idx] == max_sum:
                    count += 1
                    team = idx
            if count == 1 and team != 0:
                bonuses[team] += max_sum
                bonuses[team] %= MOD
        else:
            team = x
            split(l)
            split(r + 1)
            new_intervals = []
            i = 0
            while i < len(intervals):
                s, e, t, th = intervals[i]
                if e < l:
                    new_intervals.append(intervals[i])
                    i += 1
                elif s > r:
                    new_intervals.append(intervals[i])
                    i += 1
                else:
                    new_intervals.append(intervals[i])
                    i += 1
            intervals = new_intervals

            left = bisect.bisect_left(intervals, (l, -1, -1, -1))
            while left > 0 and intervals[left-1][1] >= l:
                left -= 1
            right = bisect.bisect_right(intervals, (r, N, 6, 1e18)) - 1
            while right < len(intervals)-1 and intervals[right+1][0] <= r:
                right += 1

            to_process = []
            for i in range(left, right + 1):
                to_process.append(intervals[i])
            del intervals[left:right+1]

            new_segments = []
            for s, e, t, th in to_process:
                a = max(s, l)
                b = min(e, r)
                if a > b:
                    new_segments.append((s, e, t, th))
                    continue
                if t == team:
                    new_th = th + 1
                else:
                    new_th = 1
                if a > s:
                    new_segments.append((s, a-1, t, th))
                new_segments.append((a, b, team, new_th))
                if b < e:
                    new_segments.append((b+1, e, t, th))
            intervals[left:left] = new_segments

            merged = []
            for interval in intervals:
                if not merged:
                    merged.append(interval)
                else:
                    last = merged[-1]
                    s, e, t, th = interval
                    if last[1] + 1 == s and last[2] == t and last[3] == th:
                        merged[-1] = (last[0], e, t, th)
                    else:
                        merged.append(interval)
            intervals = merged

    total = [0] * 6
    for s, e, t, th in intervals:
        total[t] += (e - s + 1) * th

    A = (total[1] + bonuses[1]) % MOD
    B = (total[2] + bonuses[2]) % MOD
    C = (total[3] + bonuses[3]) % MOD
    D = (total[4] + bonuses[4]) % MOD
    E = (total[5] + bonuses[5]) % MOD

    print(A, B, C, D, E)

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