結果

問題 No.631 Noelちゃんと電車旅行
コンテスト
ユーザー maspy
提出日時 2020-03-22 05:46:56
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 2,567 bytes
コンパイル時間 172 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 57,204 KB
最終ジャッジ日時 2024-12-24 16:12:12
合計ジャッジ時間 40,576 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 12 TLE * 9
権限があれば一括ダウンロードができます

ソースコード

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