結果

問題 No.255 Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:19:40
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 4,716 bytes
コンパイル時間 239 ms
コンパイル使用メモリ 82,108 KB
実行使用メモリ 274,476 KB
最終ジャッジ日時 2025-03-20 20:20:42
合計ジャッジ時間 16,251 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 MLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

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)]
    global_sums = [0] * 5  # A, B, C, D, E
    bonus_points = [0] *5
    
    for _ in range(Q):
        x = int(data[ptr])
        l = int(data[ptr+1])
        r = int(data[ptr+2])
        ptr +=3
        
        if x ==0:
            # Bonus query
            sums = [0]*5
            for iv in intervals:
                s, e, owner, cnt = iv
                if owner ==0:
                    continue
                os = max(s, l)
                oe = min(e, r)
                if os > oe:
                    continue
                length = oe - os +1
                team_idx = owner -1
                if 0 <= team_idx <5:
                    sums[team_idx] += cnt * length
            max_sum = max(sums)
            count = sums.count(max_sum)
            if count ==1 and max_sum >0:
                team_idx = sums.index(max_sum)
                bonus_points[team_idx] = (bonus_points[team_idx] + max_sum) % MOD
        else:
            team_idx = x-1  # x is 1-5, team_idx 0-4
            new_intervals = []
            to_process = []
            for iv in intervals:
                s, e, owner, cnt = iv
                if e < l or s > r:
                    new_intervals.append(iv)
                else:
                    to_process.append(iv)
            
            for iv in to_process:
                s, e, owner, cnt = iv
                left_start = s
                left_end = min(e, l-1)
                mid_start = max(s, l)
                mid_end = min(e, r)
                right_start = max(s, r+1)
                right_end = e
                if left_start <= left_end:
                    new_intervals.append( (left_start, left_end, owner, cnt) )
                if right_start <= right_end:
                    new_intervals.append( (right_start, right_end, owner, cnt) )
                
                if mid_start > mid_end:
                    continue
                mid_owner = owner
                mid_cnt = cnt
                if mid_owner == (team_idx +1):  # team_idx is 0-4, so +1 is 1-5
                    new_cnt = mid_cnt +1
                else:
                    new_owner = team_idx +1
                    new_cnt = 1
                    mid_owner = new_owner
                mid_iv = (mid_start, mid_end, mid_owner, new_cnt)
                
                # Update global sums
                mid_len = mid_end - mid_start +1
                if owner != mid_owner:
                    if owner >=1:
                        orig_team = owner -1
                        global_sums[orig_team] = (global_sums[orig_team] - cnt * mid_len) % MOD
                    global_sums[team_idx] = (global_sums[team_idx] + new_cnt * mid_len) % MOD
                else:
                    # same owner, new_cnt is cnt +1
                    global_sums[team_idx] = (global_sums[team_idx] + mid_len) % MOD
                
                # Insert mid_iv into new_intervals and merge
                pos = bisect.bisect_left(new_intervals, (mid_iv[0],))
                new_intervals.insert(pos, mid_iv)
                
                # Check left
                while pos >0:
                    left = new_intervals[pos-1]
                    if left[1] >= mid_iv[0] -1 and left[2] == mid_iv[2] and left[3] == mid_iv[3]:
                        merged = (left[0], mid_iv[1], left[2], left[3])
                        new_intervals.pop(pos-1)
                        new_intervals.pop(pos-1)
                        new_intervals.insert(pos-1, merged)
                        pos -=1
                        mid_iv = merged
                    else:
                        break
                # Check right
                while pos < len(new_intervals)-1:
                    right = new_intervals[pos+1]
                    if mid_iv[1] >= right[0] -1 and right[2] == mid_iv[2] and right[3] == mid_iv[3]:
                        merged = (mid_iv[0], right[1], mid_iv[2], mid_iv[3])
                        new_intervals.pop(pos)
                        new_intervals.pop(pos)
                        new_intervals.insert(pos, merged)
                        mid_iv = merged
                    else:
                        break
            intervals.clear()
            intervals.extend(sorted(new_intervals, key=lambda x: x[0]))
    
    # Calculate final scores
    final = [ (global_sums[i] + bonus_points[i]) % MOD for i in range(5)]
    print(' '.join(map(str, final)))

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