結果

問題 No.3017 交互浴
コンテスト
ユーザー D M
提出日時 2025-02-05 15:00:55
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,634 bytes
コンパイル時間 635 ms
コンパイル使用メモリ 81,792 KB
実行使用メモリ 345,600 KB
最終ジャッジ日時 2025-02-05 15:03:09
合計ジャッジ時間 123,960 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20 TLE * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

def solve():
    import sys,sys
    sys.setrecursionlimit(10**6)
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    try:
        N = int(data[0])
    except:
        return
    # H_i の読み込み
    Hs = [int(x) for x in data[1:1+N]]
    
    # 座標圧縮: 更新するのは [0, H]．
    coords_set = {0}
    for h in Hs:
        coords_set.add(h)
    coords = sorted(coords_set)
    comp = {}
    for i, c in enumerate(coords):
        comp[c] = i
    # セグメントツリーで扱う区間は，リーフ i が [coords[i], coords[i+1]) を表す
    nseg = len(coords) - 1  # リーフの個数
    
    # 遅延評価付きセグメントツリー用の配列（サイズは 4*nseg 程度）
    size = 4 * (nseg + 1)
    seg = [0] * size        # 各ノードが表す区間内の「青になっている長さ」
    lazy = [None] * size    # lazy[node] が None でなければ，その区間は一様に色 val (1:青，0:緑)
    seglen_arr = [0] * size # 各ノードが表す区間の全長
    
    # セグメントツリー構築（区間 [l, r) は coords[l] から coords[r] まで）
    def build(node, l, r):
        seglen_arr[node] = coords[r] - coords[l]
        lazy[node] = None
        if r - l == 1:
            # 葉ノード：初期色は全て緑 → 値 0
            seg[node] = 0
        else:
            mid = (l + r) >> 1
            build(node*2, l, mid)
            build(node*2+1, mid, r)
            seg[node] = seg[node*2] + seg[node*2+1]
    if nseg > 0:
        build(1, 0, nseg)
    
    # lazy 情報を子ノードに伝播
    def push(node, l, r):
        if lazy[node] is not None and r - l > 1:
            mid = (l + r) >> 1
            lazy[node*2] = lazy[node]
            seg[node*2] = seglen_arr[node*2] if lazy[node] == 1 else 0
            lazy[node*2+1] = lazy[node]
            seg[node*2+1] = seglen_arr[node*2+1] if lazy[node] == 1 else 0
            lazy[node] = None

    # 区間 [ql, qr) を一様に val (1:青, 0:緑) に更新する
    def update(node, l, r, ql, qr, val):
        if ql <= l and r <= qr:
            lazy[node] = val
            seg[node] = seglen_arr[node] if val == 1 else 0
            return
        push(node, l, r)
        mid = (l + r) >> 1
        if ql < mid:
            update(node*2, l, mid, ql, qr, val)
        if qr > mid:
            update(node*2+1, mid, r, ql, qr, val)
        seg[node] = seg[node*2] + seg[node*2+1]

    # 区間 [ql, qr) の青の長さの合計を返す
    def query(node, l, r, ql, qr):
        if ql <= l and r <= qr:
            return seg[node]
        push(node, l, r)
        mid = (l + r) >> 1
        res = 0
        if ql < mid:
            res += query(node*2, l, mid, ql, qr)
        if qr > mid:
            res += query(node*2+1, mid, r, ql, qr)
        return res

    # painted_range：これまでに更新された「下側の連続部分」が [0, coords[current_range]) に相当する
    current_range = 0
    out_lines = []
    # 入浴を 1-indexed で処理．
    # 奇数回：水色（青，値＝1），偶数回：緑（値＝0）
    for i, h in enumerate(Hs, start=1):
        pos = comp[h]   # h は必ず coords に含まれているので，coords[pos]==h
        new_color = 1 if (i & 1) else 0
        # リーフで表すと，[0, pos) が更新対象．
        update(1, 0, nseg, 0, pos, new_color)
        if pos > current_range:
            current_range = pos
        ans = query(1, 0, nseg, 0, current_range)
        out_lines.append(str(ans))
    sys.stdout.write("\n".join(out_lines))

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