結果

問題 No.776 A Simple RMQ Problem
ユーザー maspymaspy
提出日時 2020-05-01 12:15:36
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,798 ms / 3,000 ms
コード長 2,660 bytes
コンパイル時間 294 ms
コンパイル使用メモリ 81,536 KB
実行使用メモリ 167,804 KB
最終ジャッジ日時 2024-12-23 18:02:30
合計ジャッジ時間 53,074 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
51,968 KB
testcase_01 AC 40 ms
52,096 KB
testcase_02 AC 678 ms
92,032 KB
testcase_03 AC 1,471 ms
125,976 KB
testcase_04 AC 1,548 ms
122,412 KB
testcase_05 AC 2,439 ms
154,424 KB
testcase_06 AC 1,193 ms
106,912 KB
testcase_07 AC 1,872 ms
136,680 KB
testcase_08 AC 2,009 ms
132,832 KB
testcase_09 AC 934 ms
112,300 KB
testcase_10 AC 1,510 ms
116,856 KB
testcase_11 AC 2,153 ms
146,300 KB
testcase_12 AC 2,549 ms
160,436 KB
testcase_13 AC 2,384 ms
158,644 KB
testcase_14 AC 2,401 ms
159,528 KB
testcase_15 AC 2,550 ms
161,448 KB
testcase_16 AC 2,517 ms
160,684 KB
testcase_17 AC 2,798 ms
136,756 KB
testcase_18 AC 2,021 ms
167,804 KB
testcase_19 AC 1,656 ms
149,184 KB
testcase_20 AC 1,763 ms
136,848 KB
testcase_21 AC 1,659 ms
150,480 KB
testcase_22 AC 1,629 ms
134,676 KB
testcase_23 AC 2,582 ms
149,672 KB
testcase_24 AC 1,931 ms
138,292 KB
testcase_25 AC 115 ms
86,400 KB
testcase_26 AC 1,839 ms
162,220 KB
testcase_27 AC 1,612 ms
165,424 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

class SegTree:
    def __init__(self, N, X_f, X_unit, X_commutative=False):
        self.N = N
        self.X_f = X_f
        self.X_unit = X_unit
        self.X = [self.X_unit] * (N + N)
        if X_commutative:
            self.fold = self._fold_commutative

    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = x
        for i in range(self.N - 1, 0, -1):
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def set_val(self, i, x):
        i += self.N
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def fold(self, L, R):
        L += self.N
        R += self.N
        vL = vR = self.X_unit
        while L < R:
            if L & 1:
                vL = self.X_f(vL, self.X[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.X_f(self.X[R], vR)
            L >>= 1
            R >>= 1
        return self.X_f(vL, vR)

    def _fold_commutative(self, L, R):
        L += self.N
        R += self.N
        v = self.X_unit
        while L < R:
            if L & 1:
                v = self.X_f(v, self.X[L])
                L += 1
            if R & 1:
                R -= 1
                v = self.X_f(v, self.X[R])
            L >>= 1
            R >>= 1
        return v

X_unit = None


def X_f(x, y):
    if x is None:
        return y
    if y is None:
        return x
    return (max(x[0], y[0], x[2] + y[1]), max(x[1], x[3] + y[1]),
            max(y[2], x[2] + y[3]), x[3] + y[3])

N, Q = map(int, readline().split())
A = map(int, readline().split())
seg = SegTree(N, X_f, X_unit)
seg.build((x, x, x, x) for x in A)

def range_max(L1, L2, R1, R2):
    R1 = max(L1, R1)
    L2 = min(L2, R2)
    if L2 < R1:
        mid = 0 if R1 == L2 + 1 else seg.fold(L2 + 1, R1)[3]
        return seg.fold(L1, L2 + 1)[2] + mid + seg.fold(R1, R2 + 1)[1]
    ret = -10**18
    # R1 より左に左端がある
    if L1 < R1:
        ret = max(ret, seg.fold(L1, R1)[2] + seg.fold(R1, R2 + 1)[1])
    # L2 以前に右端がある
    ret = max(ret, seg.fold(R1, L2 + 1)[0])
    # L2 より右に右端がある
    if L2 < R2:
        ret = max(ret, seg.fold(R1, L2 + 1)[2] + seg.fold(L2 + 1, R2 + 1)[1])
    return ret

for query in readlines():
    if query.startswith(b's'):
        i, x = map(int, query[4:].split())
        seg.set_val(i - 1, (x, x, x, x))
    else:
        print(range_max(*map(lambda x: int(x) - 1, query[4:].split())))
0