結果

問題 No.833 かっこいい電車
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 13:52:19
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,382 bytes
コンパイル時間 234 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 128,048 KB
最終ジャッジ日時 2025-06-12 13:53:37
合計ジャッジ時間 7,046 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other TLE * 1 -- * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(1 << 25)

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.size = 1
        while self.size < self.n:
            self.size <<= 1
        self.tree = [0] * (2 * self.size)
        for i in range(self.n):
            self.tree[self.size + i] = data[i]
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]
    
    def update(self, pos, val):
        pos += self.size
        self.tree[pos] = val
        while pos > 1:
            pos >>= 1
            self.tree[pos] = self.tree[2 * pos] + self.tree[2 * pos + 1]
    
    def add(self, pos, delta):
        pos += self.size
        self.tree[pos] += delta
        while pos > 1:
            pos >>= 1
            self.tree[pos] = self.tree[2 * pos] + self.tree[2 * pos + 1]
    
    def query(self, l, r):
        res = 0
        l += self.size
        r += self.size
        while l < r:
            if l % 2 == 1:
                res += self.tree[l]
                l += 1
            if r % 2 == 1:
                r -= 1
                res += self.tree[r]
            l >>= 1
            r >>= 1
        return res

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    Q = int(input[idx])
    idx += 1
    A = list(map(int, input[idx:idx+N]))
    idx += N

    prev = [None] * (N + 2)  # 1-based indices
    next_ = [None] * (N + 2)

    st = SegmentTree(A)

    for _ in range(Q):
        query = input[idx]
        x = int(input[idx + 1])
        idx += 2
        if query == '1':  # connect x
            if next_[x] == x + 1:
                continue
            if prev[x + 1] is None and next_[x] is None:
                next_[x] = x + 1
                prev[x + 1] = x
        elif query == '2':  # separate x
            if prev[x + 1] == x:
                prev[x + 1] = None
                next_[x] = None
        elif query == '3':  # remodel x
            st.add(x - 1, 1)  # SegmentTree is 0-based
        elif query == '4':  # attractiveness x
            l = x
            while prev[l] is not None:
                l = prev[l]
            r = x
            while next_[r] is not None:
                r = next_[r]
            res = st.query(l - 1, r)
            print(res)

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