結果

問題 No.631 Noelちゃんと電車旅行
ユーザー maspymaspy
提出日時 2020-03-22 05:46:56
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
TLE  
実行時間 -
コード長 2,567 bytes
コンパイル時間 299 ms
コンパイル使用メモリ 11,160 KB
実行使用メモリ 45,368 KB
最終ジャッジ日時 2023-08-26 02:45:52
合計ジャッジ時間 21,117 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,536 ms
26,588 KB
testcase_01 TLE -
testcase_02 TLE -
testcase_03 TLE -
testcase_04 TLE -
testcase_05 TLE -
testcase_06 AC 1,048 ms
23,656 KB
testcase_07 AC 483 ms
19,592 KB
testcase_08 TLE -
testcase_09 TLE -
testcase_10 AC 1,731 ms
33,796 KB
testcase_11 AC 1,471 ms
29,388 KB
testcase_12 AC 1,965 ms
36,300 KB
testcase_13 AC 1,731 ms
28,452 KB
testcase_14 AC 584 ms
16,020 KB
testcase_15 AC 1,475 ms
25,784 KB
testcase_16 AC 18 ms
8,568 KB
testcase_17 AC 18 ms
8,364 KB
testcase_18 AC 18 ms
8,508 KB
testcase_19 AC 19 ms
8,544 KB
testcase_20 AC 18 ms
8,616 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