結果

問題 No.3017 交互浴
コンテスト
ユーザー D M
提出日時 2025-02-05 15:03:53
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,965 bytes
コンパイル時間 701 ms
コンパイル使用メモリ 82,372 KB
実行使用メモリ 371,524 KB
最終ジャッジ日時 2025-02-05 15:04:37
合計ジャッジ時間 36,688 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 50 TLE * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

def solve():
    import sys, bisect
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    N = int(data[0])
    # H_i の読み込み
    Hs = [int(x) for x in data[1:1+N]]
    
    # 状態管理：segments と endpoints
    # segments はリスト [(L, R, col)]，端点 endpoints[i] = R (区間 [L, R) の右端)
    # 状態は常に [0, current_max) をカバーする（current_max は segments[-1][1]）
    segments = []     # 初めは状態未定義（まだ入浴していない状態は全身緑だが，水色部分は 0 なので管理不要）
    endpoints = []    # 各区間の右端
    current_max = 0
    waterblue = 0   # 現在の水色の全長
    
    out_lines = []
    # 1-indexed 入浴
    for i, h in enumerate(Hs, start=1):
        # 入浴 i の色: 奇数→水色 (1), 偶数→緑 (0)
        new_col = 1 if (i & 1) else 0
        
        if current_max < h:
            # [0, h) を新色に更新．
            # 以前の状態（[0, current_max)）は全て上書き，さらに [current_max, h) を新たに拡張．
            segments = [(0, h, new_col)]
            endpoints = [h]
            current_max = h
            waterblue = h if new_col == 1 else 0
        else:
            # current_max >= h
            # 旧状態：segments で表す [0, current_max) のうち，[0, h) を新色に上書きする．
            # まず，更新前の [0, h) の水色長を求める
            # segments は [0, current_max) で連続している．
            # 右端のリスト endpoints を使って，更新区間 h が含まれる区間の位置 pos を求める
            pos = bisect.bisect_left(endpoints, h)
            # ここで，pos は segments[pos] が h を超える（または等しい）区間であることを意味する．
            removed_blue = 0
            # 先頭から pos まで（pos の手前まで）は完全に [L,R) ∘ [0, h) に含まれる
            for j in range(pos):
                L, R, col = segments[j]
                if col == 1:
                    removed_blue += (R - L)
            # pos 番目（存在する場合）は部分的に上書き
            if pos < len(segments):
                L, R, col = segments[pos]
                if h > L and col == 1:
                    removed_blue += (h - L)
            # 更新後，新たに [0, h) は new_col になる．
            new_blue = h if new_col == 1 else 0
            waterblue = waterblue - removed_blue + new_blue
            
            # 状態更新：新たな状態は
            #   [0, h) : new_col
            #   もし pos 番目の区間が [L, R, col] で h < R なら，その区間の [h, R) 部分を残す．
            #   その後は segments[pos+1:] をそのまま残す．
            new_segments = [(0, h, new_col)]
            new_endpoints = [h]
            if pos < len(segments):
                L, R, col = segments[pos]
                if h < R:
                    new_segments.append((h, R, col))
                    new_endpoints.append(R)
                pos += 1
            # その後，pos 以降の区間を連結
            if pos < len(segments):
                new_segments.extend(segments[pos:])
                new_endpoints.extend(endpoints[pos:])
            # 状態更新
            segments = new_segments
            endpoints = new_endpoints
            # もし先頭の2区間が同色なら結合
            if len(segments) >= 2 and segments[0][2] == segments[1][2]:
                # 結合して [0, segments[1][1]) にする
                merged = (0, segments[1][1], segments[0][2])
                segments[0] = merged
                endpoints[0] = merged[1]
                del segments[1]
                del endpoints[1]
            # current_max は変化なし
        out_lines.append(str(waterblue))
    sys.stdout.write("\n".join(out_lines))

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