Problem:


Score : 100 points

Problem Statement

Consider a string of length N consisting of 0 and 1.
The score for the string is calculated as follows:

For each i (1 \leq i \leq M), a_i is added to the score if the string contains 1 at least once between the l_i-th and r_i-th characters (inclusive).

Find the maximum possible score of a string.

Constraints

All values in input are integers.

1 \leq N \leq 2 × 10^5

1 \leq M \leq 2 × 10^5

1 \leq l_i \leq r_i \leq N

|a_i| \leq 10^9

Input

Input is given from Standard Input in the following format:

N M
l_1 r_1 a_1
l_2 r_2 a_2
:
l_M r_M a_M

Output

Print the maximum possible score of a string.

Sample Input 1

5 3
1 3 10
2 4 -10
3 5 10

Sample Output 1

20

The score for 10001 is a_1 + a_3 = 10 + 10 = 20.

Sample Input 2

3 4
1 3 100
1 1 -10
2 2 -20
3 3 -30

Sample Output 2

90

The score for 100 is a_1 + a_2 = 100 + (-10) = 90.

Sample Input 3

1 1
1 1 -10

Sample Output 3

0

The score for 0 is 0.

Sample Input 4

1 5
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000

Sample Output 4

5000000000

The answer may not fit into a 32-bit integer type.

Sample Input 5

6 8
5 5 3
1 1 10
1 6 -8
3 6 5
3 4 9
5 5 -2
1 3 -6
4 6 -7

Sample Output 5

10

For example, the score for 101000 is a_2 + a_3 + a_4 + a_5 + a_7 = 10 + (-8) + 5 + 9 + (-6) = 10.



Sample input:
5 3
1 3 10
2 4 -10
3 5 10


Sample output:
20

Submission status: Time Limit Exceeded

Solution code:
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])

Submission status: Time Limit Exceeded

Solution code:
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))

Submission status: Time Limit Exceeded

Solution code:
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))

Submission status: Time Limit Exceeded

Solution code:
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))

Submission status: Time Limit Exceeded

Solution code:
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))

Submission status: Time Limit Exceeded

Solution code:
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))

Submission status: Time Limit Exceeded

Solution code:
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))

Submission status: Time Limit Exceeded

Solution code:
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))

Submission status: Time Limit Exceeded

Solution code:
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))

Submission status: Time Limit Exceeded

Solution code:
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))

Submission status: Time Limit Exceeded

Solution code:
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))

Submission status: Time Limit Exceeded

Solution code:
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))

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

N, M = map(int, readline().split())
L = [[] for i in range(N+1)]
R = [[] for i in range(N+1)]
for i in range(M):
    l, r, a = map(int, readline().split())
    L[l-1].append((r, a))

INF = 2**31-1

LV = (N).bit_length()
N0 = 2**LV
data = [0]*(2*N0)
lazy = [0]*(2*N0)

I = []; K = []
for x in range(N0+1):
    y = N0 + x
    z = (y // (y & -y)) >> 1
    K.append(z)
    r = []
    while z:
        r.append(z)
        z >>= 1
    r.reverse()
    I.append(r)
I.append([])

J = []
for x in range(N0+1):
    y = N0 + x + 1
    z = (y // (y & -y)) - 1
    J.append(z-1 if z else 0)

def propagates(ids):
    for i in ids:
        v = lazy[i-1]
        if not v:
            continue
        lazy[2*i-1] += v; lazy[2*i] += v
        data[2*i-1] += v; data[2*i] += v
        lazy[i-1] = 0

# update [0, r)
def update(r, x):
    propagates(I[r])

    i = r
    while i:
        v = J[i-1]
        lazy[v] += x; data[v] += x
        i -= (i & -i)

    k = K[r]
    while k:
        data[k-1] = max(data[2*k-1], data[2*k])
        k >>= 1

# update[k, k+1)
def update1(k, x):
    propagates(I[k])
    k += N0
    data[k-1] += x
    while k:
        k >>= 1
        data[k-1] = max(data[2*k-1], data[2*k])


# query [0, r)
def query(r):
    return max(map(data.__getitem__, qquery(r)))

def qquery(r):
    propagates(I[r])

    while r:
        yield J[r-1]
        r -= (r & -r)

# query [k, k+1)
def query1(k, x):
    propagates(I[k])
    return data[k + N0 - 1]


for i in range(N):
    for r, a in L[i]:
        update(i+1, a)
        R[r].append((i, a))
    for l, a in R[i]:
        update(l+1, -a)
    v = query(i+1)
    update1(i+1, v)
for l, a in R[N]:
    update(l+1, -a)
sys.stdout.write("%d\n" % query(N+1))

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

N, M = map(int, readline().split())
L = [[] for i in range(N+1)]
R = [[] for i in range(N+1)]
for i in range(M):
    l, r, a = map(int, readline().split())
    L[l-1].append((r, a))

INF = 2**31-1

LV = (N).bit_length()
N0 = 2**LV
data = [0]*(2*N0)
lazy = [0]*(2*N0)

I = []; K = []
for x in range(N0+1):
    y = N0 + x
    z = (y // (y & -y)) >> 1
    K.append(z)
    r = []
    while z:
        r.append(z)
        z >>= 1
    r.reverse()
    I.append(r)
I.append([])

J = []
for x in range(N0+1):
    y = N0 + x + 1
    z = (y // (y & -y)) - 1
    J.append(z-1 if z else 0)

def propagates(ids):
    for i in ids:
        v = lazy[i-1]
        if not v:
            continue
        lazy[2*i-1] += v; lazy[2*i] += v
        data[2*i-1] += v; data[2*i] += v
        lazy[i-1] = 0

# update [0, r)
def update(r, x):
    #propagates(I[r])

    i = r
    while i:
        v = J[i-1]
        lazy[v] += x; data[v] += x
        i -= (i & -i)

    k = K[r]
    while k:
        data[k-1] = max(data[2*k-1], data[2*k]) + lazy[k-1]
        k >>= 1

# update[k, k+1)
def update1(k, x):
    #propagates(I[k])
    k += N0
    data[k-1] += x
    while k:
        k >>= 1
        data[k-1] = max(data[2*k-1], data[2*k]) + lazy[k-1]


# query [0, r)
def query(r):
    return max(map(data.__getitem__, qquery(r)))

def qquery(r):
    propagates(I[r])

    while r:
        yield J[r-1]
        r -= (r & -r)

# query [k, k+1)
def query1(k, x):
    propagates(I[k])
    return data[k + N0 - 1]


for i in range(N):
    for r, a in L[i]:
        update(i+1, a)
        R[r].append((i, a))
    for l, a in R[i]:
        update(l+1, -a)
    v = query(i+1)
    update1(i+1, v)
for l, a in R[N]:
    update(l+1, -a)
sys.stdout.write("%d\n" % query(N+1))