結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 311 ms
113,428 KB
testcase_01 AC 395 ms
115,756 KB
testcase_02 AC 400 ms
115,852 KB
testcase_03 AC 401 ms
116,008 KB
testcase_04 AC 390 ms
115,796 KB
testcase_05 AC 383 ms
115,812 KB
testcase_06 AC 226 ms
97,344 KB
testcase_07 AC 164 ms
89,996 KB
testcase_08 AC 315 ms
113,084 KB
testcase_09 AC 358 ms
112,604 KB
testcase_10 AC 283 ms
112,304 KB
testcase_11 AC 267 ms
105,204 KB
testcase_12 AC 304 ms
115,536 KB
testcase_13 AC 306 ms
106,080 KB
testcase_14 AC 200 ms
90,700 KB
testcase_15 AC 277 ms
104,692 KB
testcase_16 AC 42 ms
59,996 KB
testcase_17 AC 43 ms
60,488 KB
testcase_18 AC 42 ms
61,132 KB
testcase_19 AC 42 ms
59,948 KB
testcase_20 AC 41 ms
59,768 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