Buggy python 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])

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 python submission (verdict: Time Limit Exceeded):
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における本当の最大値

def updates(a,b,x,k,l,r):#区間[a,b)にxを加算
    
    if a==l and r==b:
        ADD[k]+=x#そのノードのADD値を更新
        return

    if a>=(r+l)//2:
        updates(a,b,x,k*2+2,(l+r)//2,r)#左側の子のみを見る
    elif b<=(r+l)//2:
        updates(a,b,x,k*2+1,l,(l+r)//2)#右側の子のみを見る
    else:
        updates(a,(l+r)//2,x,k*2+1,l,(l+r)//2)#それ以外のときは,SEG[k*2+1]とSEG[k*2+2]で場合分け
        updates((l+r)//2,b,x,k*2+2,(l+r)//2,r)

    SEG[k]=max(SEG[k*2+1]+ADD[k*2+1],SEG[k*2+2]+ADD[k*2+2])

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:
        SEG[i]=max(SEG[i*2+1]+ADD[i*2+1],SEG[i*2+2]+ADD[i*2+2])
        i=(i-1)//2

for i in range(1,N+2):

    for b,x in end[i]:
        updates(b,i,x,0,0,seg_el)#点数がもらえる区間から出たときにその分を加算

    update_solo(i,SEG[0],seg_el)#[0,i)の最大値はSEG[0](=SEG[0]+ADD[0])と一致するはず

print(SEG[0])

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 python submission (verdict: Time Limit Exceeded):
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]
#seg_el_list=[14, 6, 2, 0]

def update(k):#SEGのkより上のノードを更新（反映）
    while k>=0:
        k=(k-1)//2
        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])


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 python submission (verdict: Time Limit Exceeded):
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_el_list=[]
i=seg_el-1
while i>=0:
    seg_el_list.append(i)
    i=(i-1)//2

SEG=[0]*(2*seg_el-1)#Segment tree.色々考えると0で初期化してOKそう
ADD=[0]*(2*seg_el-1)#加算用Segment tree,SEG[k]+ADD[k]がkにおける本当の最大値

def updates(a,b,x,k,l,r):#区間[a,b)にxを加算
    
    if r<=a or b<=l:#区間[a,b)が対象区間の外にあれば終了
        return
    
    if a<=l and r<=b:
        ADD[k]+=x#そのノードのADD値を更新
        return
    
    updates(a,b,x,k*2+1,l,(l+r)>>1)#それ以外のときは,SEG[k*2+1]とSEG[k*2+2]で場合分け
    updates(a,b,x,k*2+2,(l+r)>>1,r)

    SEG[k]=max(SEG[k*2+1]+ADD[k*2+1],SEG[k*2+2]+ADD[k*2+2])

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

for i in range(1,N+2):
    i_bit=i.bit_length()
    min_seg_el=seg_el_list[i_bit]

    for b,x in end[i]:
        updates(b,i,x,min_seg_el,0,1<<i_bit)#点数がもらえる区間から出たときにその分を加算

    update_solo(i,SEG[min_seg_el]+ADD[min_seg_el])#[0,i)の最大値はSEG[0]+ADD[0]と一致するはず

print(SEG[min_seg_el]+ADD[min_seg_el])


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 python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

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

end=[[] for i in range(N+2)]
LIST=set()#更新が必要な座標を選ぶ

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

#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における本当の最大値

def updates(a,b,x,k,l,r):#区間[a,b)にxを加算
    
    if r<=a or b<=l:#区間[a,b)が対象区間の外にあれば終了
        return
    
    if a<=l and r<=b:
        ADD[k]+=x#そのノードのADD値を更新
        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)

    SEG[k]=max(SEG[k*2+1]+ADD[k*2+1],SEG[k*2+2]+ADD[k*2+2])

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:
        SEG[i]=max(SEG[i*2+1]+ADD[i*2+1],SEG[i*2+2]+ADD[i*2+2])
        i=(i-1)//2

for i in sorted(LIST) :

    for b,x in end[i]:
        updates(b,i,x,0,0,seg_el)#点数がもらえる区間から出たときにその分を加算

    update_solo(i,SEG[0]+ADD[0],seg_el)#[0,i)の最大値はSEG[0]+ADD[0]と一致するはず

print(SEG[0]+ADD[0])


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 python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

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

end=[[] for i in range(N+2)]
LIST=set()#更新が必要な座標を選ぶ

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

LIST=sorted(LIST)

#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における本当の最大値

def updates(a,b,x,k,l,r):#区間[a,b)にxを加算
    
    if r<=a or b<=l:#区間[a,b)が対象区間の外にあれば終了
        return
    
    if a<=l and r<=b:
        ADD[k]+=x#そのノードのADD値を更新
        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)

    SEG[k]=max(SEG[k*2+1]+ADD[k*2+1],SEG[k*2+2]+ADD[k*2+2])

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:
        SEG[i]=max(SEG[i*2+1]+ADD[i*2+1],SEG[i*2+2]+ADD[i*2+2])
        i=(i-1)//2

for i in LIST:

    for b,x in end[i]:
        updates(b,i,x,0,0,seg_el)#点数がもらえる区間から出たときにその分を加算

    update_solo(i,SEG[0]+ADD[0],seg_el)#[0,i)の最大値はSEG[0]+ADD[0]と一致するはず

print(SEG[0]+ADD[0])

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 python submission (verdict: Time Limit Exceeded):
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における本当の最大値

def updates(a,b,x,k,l,r):#区間[a,b)にxを加算
    
    if r<=a or b<=l:#区間[a,b)が対象区間の外にあれば終了
        return
    
    if a<=l and r<=b:
        ADD[k]+=x#そのノードのADD値を更新
        return
    
    updates(a,b,x,k*2+1,l,(l+r)>>1)#それ以外のときは,SEG[k*2+1]とSEG[k*2+2]で場合分け
    updates(a,b,x,k*2+2,(l+r)>>1,r)

    SEG[k]=max(SEG[k*2+1]+ADD[k*2+1],SEG[k*2+2]+ADD[k*2+2])

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:
        SEG[i]=max(SEG[i*2+1]+ADD[i*2+1],SEG[i*2+2]+ADD[i*2+2])
        i=(i-1)//2

for i in range(1,N+2):

    for b,x in end[i]:
        updates(b,i,x,0,0,seg_el)#点数がもらえる区間から出たときにその分を加算

    update_solo(i,SEG[0]+ADD[0],seg_el)#[0,i)の最大値はSEG[0]+ADD[0]と一致するはず

print(SEG[0]+ADD[0])

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 python submission (verdict: Time Limit Exceeded):
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)
end=[[] for i in range(N+2)]

for l,r,a in SCORE:
    end[r+1].append((l,a))
    SUM[l]+=a
    SUM[r+1]-=a

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

#遅延Segment tree
seg_el=1<<(N+1).bit_length()#Segment treeの台の要素数
seg_el2=seg_el-1#Segment treeの最下段の最初の要素
seg_el3=seg_el2//2#下から二段目の最初の要素

SEG=[0]*(2*seg_el-1)#Segment tree.色々考えると0で初期化してOKそう
LAZY=[0]*seg_el2#伝搬用Segment tree

def propagation(k):#子ノードへ伝搬
    
    if k<seg_el3 and LAZY[k]!=0:
        
        SEG[k*2+1]+=LAZY[k]
        SEG[k*2+2]+=LAZY[k]
        LAZY[k*2+1]+=LAZY[k]
        LAZY[k*2+2]+=LAZY[k]
        LAZY[k]=0

        return

    if k<seg_el2 and LAZY[k]!=0:
        
        SEG[k*2+1]+=LAZY[k]
        SEG[k*2+2]+=LAZY[k]
        LAZY[k]=0

def updates(a,b,x,k,l,r):#区間[a,b)にxを加算
    
    if r<=a or b<=l:#区間[a,b)が対象区間の外にあれば終了
        return
    
    if a<=l and r<=b:
        SEG[k]+=x#そのノードを更新
        if k<seg_el2:
            LAZY[k]+=x#後でアクセスされたときに子ノードを更新
        return

    propagation(k)#アクセスした箇所にデータが入っていたときは,評価を伝搬させる
    
    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 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 end[i]:
        updates(j[0],i,j[1],0,0,seg_el)

    update_solo(i,SEG[0],seg_el)#[0,i)の最大値はSEG[0]と一致するはず

print(SEG[0])

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 python submission (verdict: Time Limit Exceeded):
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)
end=[[] for i in range(N+2)]

for l,r,a in SCORE:
    end[r+1].append((l,a))
    SUM[l]+=a
    SUM[r+1]-=a

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

#遅延Segment tree
seg_el=1<<(N+1).bit_length()#Segment treeの台の要素数
seg_el2=seg_el-1#Segment treeの最下段の最初の要素
seg_el3=seg_el2//2#下から二段目の最初の要素

SEG=[0]*(2*seg_el-1)#Segment tree.色々考えると0で初期化してOKそう
LAZY=[0]*seg_el2#伝搬用Segment tree

def propagation(k):#子ノードへ伝搬
    
    if k<seg_el3 and LAZY[k]!=0:
        
        SEG[k*2+1]+=LAZY[k]
        SEG[k*2+2]+=LAZY[k]
        LAZY[k*2+1]+=LAZY[k]
        LAZY[k*2+2]+=LAZY[k]
        LAZY[k]=0

        return

    if k<seg_el2 and LAZY[k]!=0:
        
        SEG[k*2+1]+=LAZY[k]
        SEG[k*2+2]+=LAZY[k]
        LAZY[k]=0

def updates(a,b,x,k,l,r):#区間[a,b)にxを加算
    
    if r<=a or b<=l:#区間[a,b)が対象区間の外にあれば終了
        return
    
    if a<=l and r<=b:
        SEG[k]+=x#そのノードを更新
        if k<seg_el2:
            LAZY[k]+=x#後でアクセスされたときに子ノードを更新
        return

    propagation(k)#アクセスした箇所にデータが入っていたときは,評価を伝搬させる
    
    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 end[i]:
        updates(j[0],i,j[1],0,0,seg_el)

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

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

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 python submission (verdict: Time Limit Exceeded):
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

seg_el=1<<(N+1).bit_length()#Segment treeの台の要素数
seg_el2=seg_el-1#Segment treeの最下段の最初の要素
seg_el3=seg_el2//2#下から二段目の最初の要素

SEG=[0]*(2*seg_el-1)#Segment tree
LAZY=[0]*seg_el2#伝搬用Segment tree

def propagation(k):#子ノードへ伝搬
    
    if k<seg_el3 and LAZY[k]!=0:
        
        SEG[k*2+1]+=LAZY[k]
        SEG[k*2+2]+=LAZY[k]
        LAZY[k*2+1]+=LAZY[k]
        LAZY[k*2+2]+=LAZY[k]
        LAZY[k]=0

        return

    if k<seg_el2 and LAZY[k]!=0:
        
        SEG[k*2+1]+=LAZY[k]
        SEG[k*2+2]+=LAZY[k]
        LAZY[k]=0

def updates(a,b,x,k,l,r):#区間[a,b)にxを加算
    
    if r<=a or b<=l:#区間[a,b)が対象区間の外にあれば終了
        return
    
    if a<=l and r<=b:
        SEG[k]+=x#そのノードを更新
        if k<seg_el2:
            LAZY[k]+=x#後でアクセスされたときに子ノードを更新
        return

    propagation(k)#アクセスした箇所にデータが入っていたときは,評価を伝搬させる
    
    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]:
        updates(SCORE[j][0],SCORE[j][1]+1,-SCORE[j][2],0,0,seg_el)
    for j in end[i]:
        updates(SCORE[j][0],SCORE[j][1]+1,SCORE[j][2],0,0,seg_el)

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

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

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 python submission (verdict: Time Limit Exceeded):
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

seg_el=1<<18#Segment treeの台の要素数
seg_el2=seg_el-1#Segment treeの最下段の最初の要素
seg_el3=seg_el2//2#下から二段目の最初の要素

SEG=[0]*(2*seg_el-1)#Segment tree
LAZY=[0]*seg_el2#伝搬用Segment tree

def propagation(k):#子ノードへ伝搬
    
    if k<seg_el3 and LAZY[k]!=0:
        
        SEG[k*2+1]+=LAZY[k]
        SEG[k*2+2]+=LAZY[k]
        LAZY[k*2+1]+=LAZY[k]
        LAZY[k*2+2]+=LAZY[k]
        LAZY[k]=0

        return

    if k<seg_el2 and LAZY[k]!=0:
        
        SEG[k*2+1]+=LAZY[k]
        SEG[k*2+2]+=LAZY[k]
        LAZY[k]=0

def updates(a,b,x,k,l,r):#区間[a,b)にxを加算
    
    if r<=a or b<=l:#区間[a,b)が対象区間の外にあれば終了
        return
    
    if a<=l and r<=b:
        SEG[k]+=x#そのノードを更新
        if k<seg_el2:
            LAZY[k]+=x#後でアクセスされたときに子ノードを更新
        return

    propagation(k)#アクセスした箇所にデータが入っていたときは,評価を伝搬させる
    
    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


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

    updates(i,i+1,getvalues(0,i,0,0,seg_el)+SUM[i],0,0,seg_el)

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


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 python submission (verdict: Time Limit Exceeded):
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)]
LIST=[]

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]
    LIST.append(SCORE[i][0])
    LIST.append(SCORE[i][1]+1)

LIST=sorted(set(LIST))

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


#遅延Segment tree

seg_el=1<<18#Segment treeの台の要素数
seg_el2=seg_el-1#Segment treeの最下段の最初の要素
seg_el3=seg_el2//2#下から二段目の最初の要素

SEG=[0]*(2*seg_el-1)#Segment tree
LAZY=[0]*seg_el2#伝搬用Segment tree

def propagation(k):#子ノードへ伝搬
    
    if k<seg_el3 and LAZY[k]!=0:
        
        SEG[k*2+1]+=LAZY[k]
        SEG[k*2+2]+=LAZY[k]
        LAZY[k*2+1]+=LAZY[k]
        LAZY[k*2+2]+=LAZY[k]
        LAZY[k]=0

        return

    if k<seg_el2 and LAZY[k]!=0:
        
        SEG[k*2+1]+=LAZY[k]
        SEG[k*2+2]+=LAZY[k]
        LAZY[k]=0

def updates(a,b,x,k,l,r):#区間[a,b)にxを加算
    
    if r<=a or b<=l:#区間[a,b)が対象区間の外にあれば終了
        return
    
    if a<=l and r<=b:
        SEG[k]+=x#そのノードを更新
        if k<seg_el2:
            LAZY[k]+=x#後でアクセスされたときに子ノードを更新
        return

    propagation(k)#アクセスした箇所にデータが入っていたときは,評価を伝搬させる
    
    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


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

    updates(i,i+1,getvalues(0,i,0,0,seg_el)+SUM[i],0,0,seg_el)

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

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 python submission (verdict: Time Limit Exceeded):
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<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))

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 python 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))
    


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 python submission (verdict: Time Limit Exceeded):
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

seg_el=1<<18#Segment treeの台の要素数
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


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)

    updates(i,i+1,getvalues(0,i,0,0,seg_el)+SUM[i],0,0,seg_el)

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

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 python submission (verdict: Time Limit Exceeded):
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

seg_el=1<<18#Segment treeの台の要素数
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))

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 python submission (verdict: Time Limit Exceeded):
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=[0 for i in range(2*seg_el-1)]#Segment tree
LAZY=[0 for i in range(2*seg_el-1)]#子ノードへの伝搬用Segment tree

def propagation(k):#一つ下の子へ伝搬
    lazy_item,LAZY[k]=LAZY[k],0
    if 0<=k<seg_el-1:
        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 update(a,b,x,k,l,r):
    if LAZY[k]!=0:#アクセスした箇所にデータが入っていたときは,評価を伝搬させる
        propagation(k)      
    if r<=a or b<=l:#区間[a,b)が対象区間の外にあれば終了
        return 
    if a<=l and r<=b:
        SEG[k]+=x
        LAZY[k]+=x#後でアクセスされたときにそのノードと子ノードを更新
        return 
    update(a,b,x,k*2+1,l,(l+r)//2)#それ以外のときは,SEG[k*2+1]とSEG[k*2+2]で場合分け
    update(a,b,x,k*2+2,(l+r)//2,r)
    SEG[k]=max(SEG[k*2+1],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 LAZY[k]!=0:#アクセスした箇所にデータが入っていたときは,評価を伝搬させる
        propagation(k)
    if a<=l and r<=b:#区間[a,b)が対象区間の中にあればSEG[k]を出力
        return SEG[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)
    return max(vl,vr)


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

    update(i,i+1,getvalues(0,i,0,0,seg_el)+SUM[i],0,0,seg_el)


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


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 python submission (verdict: Time Limit Exceeded):
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=[0 for i in range(2*seg_el-1)]#Segment tree
LAZY=[0 for i in range(2*seg_el-1)]#子ノードへの伝搬用Segment tree

def propagation(k):#一つ下の子へ伝搬
    lazy_item,LAZY[k]=LAZY[k],0
    if 0<=k<seg_el-1:
        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 update(a,b,x,k,l,r):
    if LAZY[k]!=0:#アクセスした箇所にデータが入っていたときは,評価を伝搬させる
        propagation(k)      
    if r<=a or b<=l:#区間[a,b)が対象区間の外にあれば終了
        return 
    if a<=l and r<=b:
        SEG[k]+=x
        LAZY[k]+=x#そのノードを更新&後でアクセスされたときに子ノードを更新
        return 
    update(a,b,x,k*2+1,l,(l+r)//2)#それ以外のときは,SEG[k*2+1]とSEG[k*2+2]で場合分け
    update(a,b,x,k*2+2,(l+r)//2,r)
    SEG[k]=max(SEG[k*2+1],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]
    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)
    return max(vl,vr)


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

    update(i,i+1,getvalues(0,i,0,0,seg_el)+SUM[i],0,0,seg_el)

    #print(SEG)

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


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 python submission (verdict: Time Limit Exceeded):
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=[0 for i in range(2*seg_el-1)]#Segment tree
LAZY=[0 for i in range(2*seg_el-1)]#子ノードへの伝搬用Segment tree

def propagation(k):#一つ下の子へ伝搬
    lazy_item,LAZY[k]=LAZY[k],0
    if 0<=k<seg_el-1:
        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 update(a,b,x,k,l,r):
    if LAZY[k]!=0:#アクセスした箇所にデータが入っていたときは,評価を伝搬させる
        propagation(k)
        
    if r<=a or b<=l:#区間[a,b)が対象区間の外にあれば終了
        return 
    if a<=l and r<=b:
        SEG[k]+=x
        LAZY[k]+=x#そのノードを更新&後でアクセスされたときに子ノードを更新
        return 
    update(a,b,x,k*2+1,l,(l+r)//2)#それ以外のときは,SEG[k*2+1]とSEG[k*2+2]で場合分け
    update(a,b,x,k*2+2,(l+r)//2,r)
    SEG[k]=max(SEG[k*2+1],SEG[k*2+2])#そのノードを更新（再帰的に値が求まる）

def getvalues(a,b,k,l,r):#区間[a,b)での,SEG[k],つまり区間[l,r)に関する最大値を調べる
    if LAZY[k]!=0:#アクセスした箇所にデータが入っていたときは,評価を伝搬させる
        propagation(k)
    if r<=a or b<=l:#区間[a,b)が対象区間の外にあれば,-infを出力
        return 0
    if a<=l and r<=b:#区間[a,b)が対象区間の中にあればSEG[k]を出力
        return SEG[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)
    return max(vl,vr)


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

    update(i,i+1,getvalues(0,i,0,0,seg_el)+SUM[i],0,0,seg_el)

    #print(SEG)

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


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 python submission (verdict: Time Limit Exceeded):
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=[0 for i in range(2*seg_el-1)]#Segment tree
LAZY=[0 for i in range(2*seg_el-1)]#子ノードへの伝搬用Segment tree

def propagation(k):#一つ下の子へ伝搬
    lazy_item,LAZY[k]=LAZY[k],0
    if 0<=k<seg_el-1:
        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 update(a,b,x,k,l,r):
    if LAZY[k]!=0:#アクセスした箇所にデータが入っていたときは,評価を伝搬させる
        propagation(k)
        
    if r<=a or b<=l:#区間[a,b)が対象区間の外にあれば終了
        return 
    if a<=l and r<=b:
        SEG[k]+=x
        LAZY[k]+=x#そのノードを更新&後でアクセスされたときに子ノードを更新
        return 
    update(a,b,x,k*2+1,l,(l+r)//2)#それ以外のときは,SEG[k*2+1]とSEG[k*2+2]で場合分け
    update(a,b,x,k*2+2,(l+r)//2,r)
    SEG[k]=max(SEG[k*2+1],SEG[k*2+2])#そのノードを更新（再帰的に値が求まる）

def getvalues(a,b,k,l,r):#区間[a,b)での,SEG[k],つまり区間[l,r)に関する最大値を調べる
    if LAZY[k]!=0:#アクセスした箇所にデータが入っていたときは,評価を伝搬させる
        propagation(k)
    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]
    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)
    return max(vl,vr)


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

    update(i,i+1,getvalues(0,i,0,0,seg_el)+SUM[i],0,0,seg_el)

    #print(SEG)

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

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])