Problem p03182 (python)

Fixed submission:
import sys
input = sys.stdin.readline

N,M=map(int,input().split())

end=[[] for i in range(N+2)]

for i in [0]*M:
    l,r,a=map(int,input().split())
    end[r+1].append((l,a))

#Starry Sky tree
seg_el=1<<18#Segment treeの台の要素数

SEG=[0]*(2*seg_el-1)#Segment tree.色々考えると0で初期化してOKそう
ADD=[0]*(2*seg_el-1)#加算用Segment tree,SEG[k]+ADD[k]がkにおける本当の最大値
seg_el_list=[524286, 262142, 131070, 65534, 32766, 16382, 8190, 4094, 2046, 1022, 510, 254, 126, 62, 30, 14, 6, 2, 0]

def update(k):#SEGのkより上のノードを更新（反映）
    while k>=0:
        k=(k-1)//2
        if SEG[k]==max(SEG[k*2+1]+ADD[k*2+1],SEG[k*2+2]+ADD[k*2+2]):
            break
        SEG[k]=max(SEG[k*2+1]+ADD[k*2+1],SEG[k*2+2]+ADD[k*2+2])

def to_seg(a):#aが終点となる区間をSegment treeの座標へ変換  
    b=(a&(-a)).bit_length()
    return seg_el_list[b]+a//(1<<(b-1))

def add(a,b,x):#区間(a,b]にxを加算
    #print(a,b,x)
    while b!=0:
        ADD[to_seg(b)]+=x
        update(to_seg(b))
        b-=(b&(-b))

    while a!=0:
        ADD[to_seg(a)]+=-x
        update(to_seg(a))
        a-=(a&(-a))
    
for i in range(N+2):
    for b,k in end[i]:
        add(b,i,k)#点数がもらえる区間から出たときにその分を加算

    SEG[i+seg_el-1]=SEG[0]
    update(i+seg_el-1)

print(SEG[0])

Buggy submission (verdict: Runtime Error):
#Starry Sky tree
seg_el=1<<18#Segment treeの台の要素数

SEG=[0]*(2*seg_el-1)#Segment tree.色々考えると0で初期化してOKそう
ADD=[0]*(2*seg_el-1)#加算用Segment tree,SEG[k]+ADD[k]がkにおける本当の最大値
seg_el_list=[524286, 262142, 131070, 65534, 32766, 16382, 8190, 4094, 2046, 1022, 510, 254, 126, 62, 30, 14, 6, 2, 0]

def update(k):#SEGのkより上のノードを更新（反映）
    while k>=0:
        k=(k-1)//2
        if SEG[k]==max(SEG[k*2+1]+ADD[k*2+1],SEG[k*2+2]+ADD[k*2+2]):
            break
        SEG[k]=max(SEG[k*2+1]+ADD[k*2+1],SEG[k*2+2]+ADD[k*2+2])

def to_seg(a):#aが終点となる区間をSegment treeの座標へ変換  
    b=(a&(-a)).bit_length()
    return seg_el_list[b]+a//(1<<(b-1))

def add(a,b,x):#区間(a,b]にxを加算
    #print(a,b,x)
    while b!=0:
        ADD[to_seg(b)]+=x
        update(to_seg(b))
        b-=(b&(-b))

    while a!=0:
        ADD[to_seg(a)]+=-x
        update(to_seg(a))
        a-=(a&(-a))
    
for i in range(N+2):
    for b,k in end[i]:
        add(b,i,k)#点数がもらえる区間から出たときにその分を加算

    SEG[i+seg_el-1]=SEG[0]
    update(i+seg_el-1)

print(SEG[0])

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

N,M=map(int,input().split())
SCORE=[list(map(int,input().split())) for i in range(M)]

SUM=[0]*(N+2)
start=[[] for i in range(N+2)]
end=[[] for i in range(N+2)]

for i in range(M):
    start[SCORE[i][0]].append(i)
    end[SCORE[i][1]+1].append(i)
    SUM[SCORE[i][0]]+=SCORE[i][2]
    SUM[SCORE[i][1]+1]-=SCORE[i][2]

import itertools
SUM=list(itertools.accumulate(SUM))


#遅延Segment tree

for i in range(30):#要素数以上の2のベキを見つける
    if N<1<<i:
        seg_el=1<<i#Segment treeの台の要素数
        break

seg_el2=seg_el-1#Segment treeの一段目の最初の要素

SEG=[0]*(2*seg_el-1)#Segment tree
LAZY=[0]*(2*seg_el-1)#子ノードへの伝搬用Segment tree

def propagation(k):#子ノードへ伝搬
    
    if LAZY[k]!=0 and k<seg_el2:
        lazy_item=LAZY[k]
        LAZY[k]=0

        LAZY[k*2+1]+=lazy_item
        LAZY[k*2+2]+=lazy_item
        SEG[k*2+1]+=lazy_item
        SEG[k*2+2]+=lazy_item

def updates(a,b,x,k,l,r):#区間[a,b)にxを加算
    propagation(k)#アクセスした箇所にデータが入っていたときは,評価を伝搬させる
    
    if r<=a or b<=l:#区間[a,b)が対象区間の外にあれば終了
        return
    
    if a<=l and r<=b:
        SEG[k]+=x#そのノードを更新
        LAZY[k]+=x#後でアクセスされたときに子ノードを更新
        return
    
    updates(a,b,x,k*2+1,l,(l+r)//2)#それ以外のときは,SEG[k*2+1]とSEG[k*2+2]で場合分け
    updates(a,b,x,k*2+2,(l+r)//2,r)

    if SEG[k*2+1]>SEG[k*2+2]:#そのノードを更新（再帰的に値が求まる）
        SEG[k]=SEG[k*2+1]
    else:
        SEG[k]=SEG[k*2+2]


def getvalues(a,b,k,l,r):#区間[a,b)での,SEG[k],つまり区間[l,r)に関する最大値を調べる
    
    if r<=a or b<=l:#区間[a,b)が対象区間の外にあれば,-infを出力
        return -float("inf")
    
    if a<=l and r<=b:#区間[a,b)が対象区間の中にあればSEG[k]を出力
        return SEG[k]
    
    propagation(k)#アクセスした箇所にデータが入っていたときは,評価を伝搬させる
    
    vl=getvalues(a,b,k*2+1,l,(l+r)//2)#それ以外のときは,SEG[k*2+1]とSEG[k*2+2]で場合分け（木の子ノード二つを見る）
    vr=getvalues(a,b,k*2+2,(l+r)//2,r)

    if vl>vr:
        return vl
    else:
        return vr

def update_solo(n,x,seg_el):#A[n]+=xに更新（反映）
    i=n+seg_el-1
    SEG[i]+=x
    i=(i-1)//2
    
    while i>=0:
        if SEG[i*2+1]>SEG[i*2+2]:
            SEG[i]=SEG[i*2+1]
        else:
            SEG[i]=SEG[i*2+2]
        i=(i-1)//2

for i in range(1,N+2):
    
    for j in start[i]:
        l,r,s=SCORE[j]
        updates(l,r+1,-s,0,0,seg_el)
    for j in end[i]:
        l,r,s=SCORE[j]
        updates(l,r+1,s,0,0,seg_el)

    #print(SEG)

    update_solo(i,getvalues(0,i,0,0,seg_el)+SUM[i],seg_el)

    #print(SEG)


print(getvalues(0,N+1,0,0,seg_el))