結果

問題 No.631 Noelちゃんと電車旅行
ユーザー maspymaspy
提出日時 2020-03-22 05:47:16
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 447 ms / 2,000 ms
コード長 2,567 bytes
コンパイル時間 151 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 115,968 KB
最終ジャッジ日時 2024-10-02 09:44:53
合計ジャッジ時間 7,443 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 308 ms
113,408 KB
testcase_01 AC 409 ms
115,712 KB
testcase_02 AC 447 ms
115,456 KB
testcase_03 AC 397 ms
115,840 KB
testcase_04 AC 387 ms
115,456 KB
testcase_05 AC 390 ms
115,968 KB
testcase_06 AC 247 ms
97,152 KB
testcase_07 AC 188 ms
89,856 KB
testcase_08 AC 336 ms
113,280 KB
testcase_09 AC 384 ms
112,512 KB
testcase_10 AC 307 ms
112,000 KB
testcase_11 AC 288 ms
104,960 KB
testcase_12 AC 328 ms
115,712 KB
testcase_13 AC 336 ms
105,856 KB
testcase_14 AC 198 ms
90,496 KB
testcase_15 AC 264 ms
104,704 KB
testcase_16 AC 49 ms
59,392 KB
testcase_17 AC 49 ms
59,264 KB
testcase_18 AC 50 ms
59,392 KB
testcase_19 AC 50 ms
59,904 KB
testcase_20 AC 50 ms
59,264 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin/ python3.8
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


class LazySegmentTree:
    """ range add and range max"""

    def __init__(self, A):
        INF = 10 ** 18
        self.unit = -INF
        self.N = len(A)
        self.H = (self.N - 1).bit_length()
        self.W = 1 << self.H
        self.lazy = [0] * (2 * self.W)
        self.build(A)

    def build(self, A):
        W = self.W
        data = [self.unit] * (2 * W)
        for i, x in enumerate(A):
            data[W + i] = x
        for i in range(W - 1, 0, -1):
            data[i] = max(data[i << 1], data[i << 1 | 1])
        self.data = data

    def __repr__(self):
        return '\n'.join([
            f'data: {self.data}',
            f'raw_data: {self.data[self.W:self.W + self.N]}',
            f'lazy: {self.lazy}'])

    def apply(self, p, value):
        self.data[p] += value
        self.lazy[p] += value

    def build_local(self, i):
        while i > 1:
            i >>= 1
            self.data[i] = max(self.data[i << 1], self.data[i << 1 | 1]) + self.lazy[i]

    def propagate(self, p):
        for s in range(self.H, 0, -1):
            i = p >> s
            x = self.lazy[i]
            self.apply(i << 1, x)
            self.apply(i << 1 | 1, x)
            self.lazy[i] = 0

    def range_add(self, L, R, x):
        """ add x to [L,R) """
        L += self.W
        R += self.W
        L0 = L
        R0 = R
        while L < R:
            if L & 1:
                self.apply(L, x)
                L += 1
            if R & 1:
                R -= 1
                self.apply(R, x)
            L >>= 1
            R >>= 1
        self.build_local(L0)
        self.build_local(R0 - 1)

    def range_max(self, L, R):
        """ max of [L,R) """
        L += self.W
        R += self.W
        self.propagate(L)
        self.propagate(R - 1)
        ret = self.unit
        while L < R:
            if L & 1:
                x = self.data[L]
                if ret < x:
                    ret = x
                L += 1
            if R & 1:
                R -= 1
                x = self.data[R]
                if ret < x:
                    ret = x
            L >>= 1
            R >>= 1
        return ret


N = int(readline())
T = [0] + [(N - i) * 3 + x for i, x in enumerate(map(int, readline().split()), 1)]
seg = LazySegmentTree(T)
Q = int(readline())
m = map(int, read().split())
LRD = zip(m, m, m)
for L, R, D in LRD:
    seg.range_add(L, R + 1, D)
    print(seg.data[1])
0