#992965 (PyPy3) No.631 Noelちゃんと電車旅行

• 問題: No.631 Noelちゃんと電車旅行
• ユーザー: titia
• 提出日時: 2024-07-07 04:00:50
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 518 ms / 2,000 ms
• コード長: 2,839 bytes
• コンパイル時間: 1,117 ms
• コンパイル使用メモリ: 82,244 KB
• 実行使用メモリ: 93,888 KB
• 最終ジャッジ日時: 2024-07-07 04:01:03
• 合計ジャッジ時間: 9,870 ms
• ジャッジサーバーID （参考情報）: judge4 / judge1

ファイルパターン	結果
other	AC * 21

ソースコード

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
126
import sys
input = sys.stdin.readline
N=int(input())
T=list(map(int,input().split()))
# 非再帰遅延伝搬セグ木（範囲加算, 範囲最小値出力）
# 高々N点を更新
seg_el=1<<(N.bit_length()) # Segment treeの台の要素数
SEG=[0]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化
LAZY=[0]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化
def indexes(L,R): # 遅延伝搬すべきノードのリストを下から上の順に返す. （つまり, updateやgetvaluesで見るノードより上にあるノードたち）
    INDLIST=[]
    R-=1
    
    L>>=1
    R>>=1
    while L!=R:
        if L>R:
            INDLIST.append(L)
            L>>=1
        else:
            INDLIST.append(R)
            R>>=1
    while L!=0:
        INDLIST.append(L)
        L>>=1
    return INDLIST
        
def adds(l,r,x): # 区間[l,r)を +x 更新
        
    L=l+seg_el
    R=r+seg_el
    L//=(L & (-L))
    R//=(R & (-R))
    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]: # 遅延伝搬. 上から更新していく. （ただし, 今回はうまくやるとこの部分を省ける. addはクエリの順番によらないので. 
        addではなく, updateの場合必要）
        if LAZY[ind]!=0:
            plus_lazy=LAZY[ind]
            
            SEG[ind<<1]+=plus_lazy
            SEG[1+(ind<<1)]+=plus_lazy
            
            LAZY[ind<<1]+=plus_lazy
            LAZY[1+(ind<<1)]+=plus_lazy
            
            LAZY[ind]=0
    
    while L!=R:
        if L > R:
            SEG[L]+=x
            LAZY[L]+=x
            L+=1
            L//=(L & (-L))
        else:
            R-=1
            SEG[R]+=x
            LAZY[R]+=x
            R//=(R & (-R))
    for ind in UPIND:
        SEG[ind]=max(SEG[ind<<1],SEG[1+(ind<<1)]) # 最初の遅延伝搬を省いた場合, ここを変える
        
def getvalues(l,r): # 区間[l,r)に関するmaxを調べる
    L=l+seg_el
    R=r+seg_el
    L//=(L & (-L))
    R//=(R & (-R))
    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]: # 遅延伝搬
        if LAZY[ind]!=0:
            plus_lazy=LAZY[ind]
            
            SEG[ind<<1]+=plus_lazy
            SEG[1+(ind<<1)]+=plus_lazy
            
            LAZY[ind<<1]+=plus_lazy
            LAZY[1+(ind<<1)]+=plus_lazy
            
            LAZY[ind]=0
            
    ANS=0
    while L!=R:
        if L > R:
            ANS=max(ANS , SEG[L])
            L+=1
            L//=(L & (-L))
        else:
            R-=1
            ANS=max(ANS , SEG[R])
            R//=(R & (-R))
    return ANS
for i in range(N-1):
    adds(i,i+1,T[i]+(N-i-1)*3)
Q=int(input())
for tests in range(Q):
    l,r,plus=map(int,input().split())
    l-=1
    adds(l,r,plus)
    print(getvalues(0,N))
    
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX