結果

問題 No.1441 MErGe
コンテスト
ユーザー c-yan
提出日時 2021-03-28 13:32:05
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,260 bytes
コンパイル時間 316 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 240,296 KB
最終ジャッジ日時 2024-11-29 09:02:24
合計ジャッジ時間 41,604 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 8 TLE * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from sys import setrecursionlimit, stdin
from itertools import accumulate
from operator import add

class SegmentTree:
    def __init__(self, size, op, e):
        self._op = op
        self._e = e
        self._size = size
        t = 1
        while t < size:
            t *= 2
        self._offset = t - 1
        self._data = [e] * (t * 2 - 1)

    def __getitem__(self, key):
        return self._data[self._offset + key]

    def __setitem__(self, key, value):
        op = self._op
        data = self._data
        i = self._offset + key
        data[i] = value
        while i >= 1:
            i = (i - 1) // 2
            data[i] = op(data[i * 2 + 1], data[i * 2 + 2])

    def build(self, iterable):
        op = self._op
        data = self._data
        data[self._offset:self._offset + self._size] = iterable
        for i in range(self._offset - 1, -1, -1):
            data[i] = op(data[i * 2 + 1], data[i * 2 + 2])

    def query(self, start, stop):
        def iter_segments(data, l, r):
            while l < r:
                if l & 1 == 0:
                    yield data[l]
                if r & 1 == 0:
                    yield data[r - 1]
                l = l // 2
                r = (r - 1) // 2
        op = self._op
        it = iter_segments(self._data, start + self._offset,
                           stop + self._offset)
        result = self._e
        for v in it:
            result = op(result, v)
        return result

readline = stdin.readline
setrecursionlimit(10 ** 6)

N, Q = map(int, readline().split())
A = list(map(int, readline().split()))

A = list(accumulate(A))

st = SegmentTree(N + 1, add, 0)

result = []
for _ in range(Q):
    T, l, r = map(int, readline().split())
    l, r = l - 1, r - 1

    a = 0
    b = l
    while True:
        c = st.query(a, b)
        if c == 0:
            break
        a = b
        b += c
    x = b

    if T == 1:
        st[x] += r - l
    elif T == 2:
        a = 0
        b = r
        while True:
            c = st.query(a, b + 1)
            if c == 0:
                break
            a = b + 1
            b += c
        y = b
        if x != 0:
            result.append(A[y] - A[x - 1])
        else:
            result.append(A[y])
print(*result, sep='\n')
0