#720503 (PyPy3) No.865 24時間降水量

• 問題: No.865 24時間降水量
• ユーザー: brthyyjp
• 提出日時: 2021-11-28 12:39:36
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 801 ms / 2,000 ms
• コード長: 3,200 bytes
• コンパイル時間: 156 ms
• コンパイル使用メモリ: 82,376 KB
• 実行使用メモリ: 141,668 KB
• 最終ジャッジ日時: 2024-07-01 05:40:55
• 合計ジャッジ時間: 5,466 ms
• ジャッジサーバーID （参考情報）: judge5 / judge1

ファイルパターン	結果
sample	AC * 3
other	AC * 18

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
class LazySegTree:
    # RMQ and RAQ
    def __init__(self, init_val, seg_ide, lazy_ide, segfunc):
        self.n = len(init_val)
        self.num = 2**(self.n-1).bit_length()
        self.seg_ide = seg_ide
        self.lazy_ide = lazy_ide
        self.segfunc = segfunc
        # seg, lazy: 1-indexed
        self.seg = [seg_ide]*2*self.num
        for i in range(self.n):
            self.seg[i+self.num] = init_val[i]
        for i in range(self.num-1, 0, -1):
            self.seg[i] = self.segfunc(self.seg[2*i], self.seg[2*i+1])
        self.lazy = [lazy_ide]*2*self.num
    def gindex(self, l, r):
        # l, r: 1-indexed
        L = l + self.num
        R = r + self.num
        lm = (L // (L & -L)) >> 1
        rm = (R // (R & -R)) >> 1
        while L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            L = L >> 1
            R = R >> 1
        while L:
            yield L
            L = L >> 1
    def propagate(self, *ids):
        # ids: 1-indexed
        for i in reversed(ids):
            v = self.lazy[i]
            if v == self.lazy_ide:
                continue
            self.lazy[2*i] += v
            self.lazy[2*i+1] += v
            self.seg[2*i] += v
            self.seg[2*i+1] += v
            self.lazy[i] = self.lazy_ide
    def update(self, l, r, x):
        # l, r: 0-indexed
        # add x to [l, r)
        L = l + self.num
        R = r + self.num
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R] += x
                self.seg[R] += x
            if L & 1:
                self.lazy[L] += x
                self.seg[L] += x
                L += 1
            L = L >> 1
            R = R >> 1
        for i in self.gindex(l, r):
            # i: 1-indexed
            self.seg[i] = self.segfunc(self.seg[2*i], self.seg[2*i+1]) + self.lazy[i]
    def query(self, l, r):
        # l, r: 0-indexed
        # query for [l, r)
        if r <= l:
            return self.seg_ide
        self.propagate(*self.gindex(l, r))
        L = l + self.num
        R = r + self.num
        res = self.seg_ide
        while L < R:
            if R & 1:
                R -= 1
                res = self.segfunc(res, self.seg[R])
            if L & 1:
                res = self.segfunc(self.seg[L], res)
                L += 1
            L = L >> 1
            R = R >> 1
        return res
    def __str__(self): # for debug
        arr = [self.query(i,i+1) for i in range(self.n)]
        return str(arr)
import sys
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from itertools import accumulate
def main():
    n = int(input())
    A = list(map(int, input().split()))
    C = [0]+A
    C = list(accumulate(C))
    B = []
    for i in range(n):
        if i+24 <= n:
            b = C[i+24]-C[i]
            B.append(b)
    seg = LazySegTree(B, -1, 0, max)
    q = int(input())
    for i in range(q):
        t, v = map(int, input().split())
        t -= 1
        p = A[t]
        seg.update(max(0, t-23), min(seg.n, t+1), -p+v)
        A[t] = v
        print(seg.query(0, seg.n))
if __name__ == '__main__':
    main()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX