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:
"""
遅延セグメント木（区間演算、区間更新）
dat[] の要素に モノイド M をもつ
laz[] の要素に Aut(M) をもつ（ただし作用素は「右」から作用とする）
アクセスは0-indexed, 内部のツリーは 1-indexed（つまりすべての和は tree[1]）
関数は閉区間
引数：
    N: 処理する区間の長さ
    op_M = operator: モノイド演算 (max, min, __add__,ラムダ式,関数定義など)
    e_M: 単位元
    compose: 作用素を合成させる関数 (max, min, __add__,ラムダ式,関数定義など)
    funcval(x,f) = f(x) 関数適用
    ID_M: 恒等作用素
"""
""" 作用素の例：
f \mapsto min(f,-)
    compose = min
    funcval = min
    ID_M = INF = 10**18
f \mapsto max(f,-)
    compose = max
    funcval = max
    ID_M = 0
f \mapsto f (定数関数)（区間代入、最後の操作のみが影響する）
compose = lambda f,g: (f if g == ID_M else g)
funcval = lambda x,f: (x if f == ID_M else f)
ID_M = None #Noneではなく、範囲外の数にすると速くなる
"""

class lazy_segment_tree:
    def __init__(self, N, operator_M, e_M, compose, funcval, ID_M=None):
        self.compose = compose #作用素の合成（右から）
        self.ID_M = ID_M       #恒等作用素
        self.funcval = funcval #関数適用

        self.op_M = operator_M # Mの演算
        self.e_M = e_M         # Mの単位元
        ####################################
        self.height = (N-1).bit_length() #木の段数
        self.N0 = N0 = 1<<self.height #木の横幅 >= N

        self.dat = [self.e_M]*(2*N0) #データの木
        self.laz = [self.ID_M]*(2*N0) #作用素の木
        
        """
        length = [N0>>1]*N0
        for i in range(2,N0): length[i] = length[i>>1]>>1
        self.length = length #区間の長さ
        """
        
    # 長さNの配列 initial で dat を初期化
    def build(self, initial):
        self.dat[self.N0:self.N0+len(initial)] = initial[:]
        for k in range(self.N0-1,0,-1):
            self.dat[k] = self.op_M(self.dat[2*k], self.dat[2*k+1])
    
    # dat[k] に laz[k] を適用して、laz[k] を伝播
    def propagate(self,k):
        if self.laz[k] == self.ID_M: return;
        self.dat[k] = self.reflect(k)
        if self.N0 <= k:
            self.laz[k] = self.ID_M
            return
        else:
            self.laz[2*k  ] = self.compose(self.laz[2*k  ],self.laz[k])
            self.laz[2*k+1] = self.compose(self.laz[2*k+1],self.laz[k])
            self.laz[k] = self.ID_M
            return
        
    # 遅延をすべて解消する
    def propagate_all(self):
        for i in range(1,2*self.N0): self.propagate(i)
    
    # laz[k]およびその上に位置する作用素をすべて伝播
    def thrust(self,k):
        for i in range(self.height,-1,-1): self.propagate(k>>i)

    def thrust2(self,L,R):
        for i in range(self.height,0,-1):
            self.propagate(L>>i)
            if (L>>i) != R>>i:
                self.propagate(R>>i)

    # 区間[l,r]に関数 f を作用
    def update(self, l,r,f):
        l += self.N0; r += self.N0
        #まず伝播させる
        #self.thrust(l>>1); self.thrust(r>>1)
        self.thrust2(l,r)
        L = l; R = r+1
        #[l.r]に対応する区間たちに関数 f を適用
        while L < R:
            if R & 1:
                R -= 1
                self.laz[R] = self.compose(self.laz[R], f)
            if L & 1:
                self.laz[L] = self.compose(self.laz[L], f)
                L += 1
            L >>= 1; R >>= 1
        # 再計算
        #self.recalc_dat(l); self.recalc_dat(r)
        self.recalc_dat2(l,r)
        
    def reflect(self,k):
        if self.laz[k] == self.ID_M: return self.dat[k]
        else: return self.funcval(self.dat[k],self.laz[k])
        
    # dat[k] を更新したときに上部を再計算
    def recalc_dat(self,k):
        k //= 2
        while k:
            self.dat[k] = self.op_M(self.funcval(self.dat[2*k],self.laz[2*k]),self.funcval(self.dat[2*k+1],self.laz[2*k+1]))
            #self.dat[k] = self.op_M(self.reflect(2*k),self.reflect(2*k+1)))
            k //= 2

    def recalc_dat2(self,l,r):
        l //= 2; r //= 2
        while l:
            #self.dat[l] = self.op_M(self.reflect(2*l),self.reflect(2*l+1))
            self.dat[l] = self.op_M(self.funcval(self.dat[2*l],self.laz[2*l]),self.funcval(self.dat[2*l+1],self.laz[2*l+1]))
            if l != r:
                #self.dat[r] = self.op_M(self.reflect(2*r),self.reflect(2*r+1))
                self.dat[r] = self.op_M(self.funcval(self.dat[2*r],self.laz[2*r]),self.funcval(self.dat[2*r+1],self.laz[2*r+1]))
            l //= 2; r //= 2

    # val[k] を取得。
    def point_get(self, k):
        k += self.N0
        res = self.dat[k]
        while k:
            if self.laz[k] != self.ID_M:
                res = self.funcval(res, self.laz[k])
            k //= 2
        return res
    
    # values[k] = x 代入する
    def point_set(self, k,x): 
        k += self.N0
        self.thrust(k)
        self.dat[k] = x
        self.recalc_dat(k)

    # 区間[L,R]をopでまとめる
    def query(self, L,R):
        L += self.N0; R += self.N0 + 1 
        self.thrust2(L,R)
        #self.thrust(L); self.thrust(R-1)
        sl = sr = self.e_M
        while L < R:
            if R & 1:
                R -= 1
                sr = self.op_M(self.reflect(R),sr)
            if L & 1:
                sl = self.op_M(sl,self.reflect(L))
                L += 1
            L >>= 1; R >>= 1
        return self.op_M(sl,sr)


###########################################################################
###########################################################################
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.buffer.readline 

n,m = [int(i) for i in readline().split()]
lra = [tuple(int(i) for i in readline().split()) for _ in range(m)]

from operator import add, itemgetter
operator_M = max
compose = add
funcval = add
ID_M = 0
e_M = -10**18

seg = lazy_segment_tree(n+1, operator_M, e_M, compose, funcval, ID_M)
seg.build([0]+[ID_M]*(n))

#seg.build([0]*n)

ans = [] 

lra.sort(key = itemgetter(1))

j = 0
for i in range(1,n+1):
    #print(seg.laz,seg.dat,i,seg.query(0,i-1))
    seg.point_set(i,seg.query(0,i-1))
    while j < m and i == lra[j][1]:
        #print("hoge")
        seg.update(lra[j][0],lra[j][1],lra[j][2])
        j += 1

seg.propagate_all()
print(max(seg.dat[seg.N0:seg.N0+n+1]))


#print(seg.laz,seg.dat)

Submission status: Time Limit Exceeded

Solution code:
class StarrySkyTree:
    #RAQ
    def __init__(self, A, intv, initialize = True, segf = min):
        #区間は 1-indexed で管理
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv = intv
        self.segf = segf
        self.lazy = [0]*(2*self.N0)
        if initialize:
            self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)
            for i in range(self.N0-1, 0, -1):
                self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
        else:
            self.data = [intv]*(2*self.N0)
 
    def _ascend(self, k):
        k = k >> 1
        c = k.bit_length()
        for j in range(c):
            idx = k >> j
            self.data[idx] = self.segf(self.data[2*idx], self.data[2*idx+1]) \
            + self.lazy[idx]
            
    def _descend(self, k):
        k = k >> 1
        idx = 1
        c = k.bit_length()
        for j in range(1, c+1):
            idx = k >> (c - j)
            ax = self.lazy[idx]
            if not ax:
                continue
            self.lazy[idx] = 0
            self.data[2*idx] += ax
            self.data[2*idx+1] += ax
            self.lazy[2*idx] += ax
            self.lazy[2*idx+1] += ax
    
    def update(self, k, x):
        k = k + self.N0
        self.data[k] = x
        self._ascend(k)
    
    def query(self, l, r):
        L = l+self.N0
        R = r+self.N0
        Li = L//(L & -L)
        Ri = R//(R & -R)
        self._descend(Li)
        self._descend(Ri - 1)
        
        s = self.intv                                                              
        while L < R:
            if R & 1:
                R -= 1
                s = self.segf(s, self.data[R])
            if L & 1:
                s = self.segf(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s
    
    def add(self, l, r, x):
        L = l+self.N0
        R = r+self.N0
 
        Li = L//(L & -L)
        Ri = R//(R & -R)
        
        while L < R :
            if R & 1:
                R -= 1
                self.data[R] += x
                self.lazy[R] += x
            if L & 1:
                self.data[L] += x
                self.lazy[L] += x
                L += 1
            L >>= 1
            R >>= 1
        
        self._ascend(Li)
        self._ascend(Ri-1)
N, M = map(int, input().split())
s = [[] for _ in range(N)]
t = [[] for _ in range(N)]
lr = []
for i in range(M):
    l, r, a = map(int, input().split())
    s[l-1].append(i)
    t[r-1].append(i)
    lr.append((l, r, a))
S = StarrySkyTree([0]*(N+1), -10**16, True, max)
ans = 0
for i in range(1, N+1):
    for j in s[i-1]:
        S.add(0, i, lr[j][2])
    res = S.query(0, i)
    S.update(i, res)
    ans = max(ans, res)
    for j in t[i-1]:
        l, r, a = lr[j]
        S.add(0, l, -a)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class StarrySkyTree:
    #RAQ
    def __init__(self, A, intv, initialize = True, segf = min):
        #区間は 1-indexed で管理
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv = intv
        self.segf = segf
        self.lazy = [0]*(2*self.N0)
        if initialize:
            self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)
            for i in range(self.N0-1, 0, -1):
                self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
        else:
            self.data = [intv]*(2*self.N0)
 
    def _ascend(self, k):
        k = k >> 1
        c = k.bit_length()
        for j in range(c):
            idx = k >> j
            self.data[idx] = self.segf(self.data[2*idx], self.data[2*idx+1]) \
            + self.lazy[idx]
            
    def _descend(self, k):
        k = k >> 1
        idx = 1
        c = k.bit_length()
        for j in range(1, c+1):
            idx = k >> (c - j)
            ax = self.lazy[idx]
            if not ax:
                continue
            self.lazy[idx] = 0
            self.data[2*idx] += ax
            self.data[2*idx+1] += ax
            self.lazy[2*idx] += ax
            self.lazy[2*idx+1] += ax
    
    def update(self, k, x):
        k = k + self.N0
        self.data[k] = x
        self._ascend(k)
    
    def query(self, l, r):
        L = l+self.N0
        R = r+self.N0
        Li = L//(L & -L)
        Ri = R//(R & -R)
        self._descend(Li)
        self._descend(Ri - 1)
        
        s = self.intv                                                              
        while L < R:
            if R & 1:
                R -= 1
                s = self.segf(s, self.data[R])
            if L & 1:
                s = self.segf(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s
    
    def add(self, l, r, x):
        L = l+self.N0
        R = r+self.N0
 
        Li = L//(L & -L)
        Ri = R//(R & -R)
        
        while L < R :
            if R & 1:
                R -= 1
                self.data[R] += x
                self.lazy[R] += x
            if L & 1:
                self.data[L] += x
                self.lazy[L] += x
                L += 1
            L >>= 1
            R >>= 1
        
        self._ascend(Li)
        self._ascend(Ri-1)
N, M = map(int, input().split())
s = [[] for _ in range(N)]
t = [[] for _ in range(N)]
lr = []
for i in range(M):
    l, r, a = map(int, input().split())
    s[l-1].append(i)
    t[r-1].append(i)
    lr.append((l, r, a))
S = StarrySkyTree([0]*(N+1), -10**16, True, max)
ans = 0
for i in range(1, N+1):
    for j in s[i-1]:
        S.add(0, i, lr[j][2])
    res = S.query(0, i)
    S.add(i, i+1, res)
    ans = max(ans, res)
    for j in t[i-1]:
        l, r, a = lr[j]
        S.add(0, l, -a)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class StarrySkyTree:
    def __init__(self,num):
        leaf=1<<(num-1).bit_length()
        self.leaf=leaf
        self.data=[0]*leaf*2
        self.lazy=[0]*leaf*2
    def indices(self,l,r):
        L,R=l+self.leaf,r+self.leaf
        lm=(L//(L&-L))>>1
        rm=(R//(R&-R))>>1
        while L<R:
            if R<=rm:
                yield R
            if L<=lm:
                yield L
            L>>=1; R>>=1
        while L:
            yield L
            L>>=1
    def _propagates(self,*ids):
        for i in reversed(ids):
            v=self.lazy[i-1]
            if v==0:
                continue
            self.lazy[2*i-1]+=v; self.lazy[2*i]+=v
            self.data[2*i-1]+=v; self.data[2*i]+=v
            self.lazy[i-1]=0
    def add(self,l,r,x):
        L,R=l+self.leaf,r+self.leaf
        while L<R:
            if L&1:
                self.lazy[L-1]+=x; self.data[L-1]+=x
                L+=1
            if R&1:
                R-=1
                self.lazy[R-1]+=x; self.data[R-1]+=x
            L>>=1; R>>=1
        for i in self.indices(l,r):
            self.data[i-1]=max(self.data[2*i-1],self.data[2*i])+self.lazy[i-1]
    def query(self,l,r): #[l,r)
        self._propagates(*self.indices(l,r))
        L,R=l+self.leaf,r+self.leaf
        ret=-float('inf')
        while L<R:
            if L&1:
                ret=max(ret,self.data[L-1])
                L+=1
            if R&1:
                R-=1
                ret=max(ret,self.data[R-1])
            L>>=1; R>>=1
        return ret
    def show(self, n):
        for i in range(n):
            print(self.query(i, i+1))
N, M = map(int, input().split())
s = [[] for _ in range(N)]
t = [[] for _ in range(N)]
lr = []
for i in range(M):
    l, r, a = map(int, input().split())
    s[l-1].append(i)
    t[r-1].append(i)
    lr.append((l, r, a))
S = StarrySkyTree(N+1)
ans = 0
for i in range(1, N+1):
    for j in s[i-1]:
        S.add(0, i, lr[j][2])
    res = S.query(0, i)
    S.add(i, i+1, res)
    ans = max(ans, res)
    for j in t[i-1]:
        l, r, a = lr[j]
        S.add(0, l, -a)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, M = map(int, input().split())
imos = np.array([[0]*(N+1) for _ in range(N)], dtype = np.int64)
for _ in range(M):
    l, r, a = map(int, input().split())
    imos[:l, l-1]+=a
    imos[:l, r]-=a
for i in range(1, N):
    imos[:, i]+=imos[:, i-1]
dp = np.zeros(N, dtype = np.int64)
dp[0] = imos[0, 0]
for i in range(1, N):
    dp[i]=max(imos[0, i], (dp[:i]+imos[1:i+1, i]).max())
print(max(0, dp.max()))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class SegmentTree(object):
    def __init__(self,A,dot,e,comp,id,act):
        """
        A: array of monoid (M,dot,e)
        comp: composite function of Hom(M), comp(f,g)=gf
        id: identity map of M
        act: action on (Hom(M),M), act(f,a)=f(a)
        """
        n=2**((len(A)-1).bit_length())
        self.__n=n
        self.__dot=dot
        self.__e=e
        self.__comp=comp
        self.__id=id
        self.__act=act
        self.__node=[e]*(2*n)
        self.__lazy=[id]*(2*n)
        for i in range(len(A)):
            self.__node[i+n]=A[i]
        for i in range(n-1,0,-1):
            self.__node[i]=self.__dot(self.__node[2*i],self.__node[2*i+1])

    def __propagate(self,i):
        if(self.__lazy[i]==self.__id): return
        node=self.__node
        lazy=self.__lazy
        if(i<self.__n): # propagate to children
            lazy[2*i]=self.__comp(lazy[2*i],lazy[i])
            lazy[2*i+1]=self.__comp(lazy[2*i+1],lazy[i])
        node[i]=self.__act(lazy[i],node[i]) # action
        lazy[i]=self.__id

    def __ancestors_propagate(self,i):
        if(i==1): return
        i//=2
        self.__ancestors_propagate(i)
        self.__propagate(i)

    def __update_ancestors(self,i):
        while(i!=1):
            self.__propagate(i+1-2*(i%2)) # propagate the sibling of i
            i//=2
            self.__node[i]=self.__dot(self.__node[2*i],self.__node[2*i+1])

    def update(self,i,c):
        i+=self.__n
        self.__ancestors_propagate(i)
        self.__propagate(i)
        self.__node[i]=c
        self.__update_ancestors(i)

    def add(self,l,r,f):
        range,low=[],[0]*2
        l+=self.__n; r+=self.__n
        while(l<r):
            if(l%2==1):
                if(low[0]==0): low[0]=l
                range.append(l)
                l+=1
            l//=2
            if(r%2==1):
                r-=1
                range.append(r)
                if(low[1]==0): low[1]=r
            r//=2
        for i in low:
            if(i): self.__ancestors_propagate(i)
        for i in range: self.__lazy[i]=self.__comp(self.__lazy[i],f)
        for i in low:
            if(i):
                self.__propagate(i)
                self.__update_ancestors(i)

    def sum(self,l,r):
        low=[0]*2
        vl,vr=self.__e,self.__e
        l+=self.__n; r+=self.__n
        while(l<r):
            if(l%2==1):
                if(low[0]==0):
                    self.__ancestors_propagate(l)
                    low[0]=1
                self.__propagate(l)
                vl=self.__dot(vl,self.__node[l])
                l+=1
            l//=2
            if(r%2==1):
                r-=1
                if(low[1]==0):
                    self.__ancestors_propagate(r)
                    low[1]=1
                self.__propagate(r)
                vr=self.__dot(self.__node[r],vr)
            r//=2
        return self.__dot(vl,vr)

def resolve():
    n,m=map(int,input().split())
    R=[[] for _ in range(n)]
    for _ in range(m):
        l,r,a=map(int,input().split())
        l-=1; r-=1
        R[r].append((l,a))
    from operator import add
    dp=SegmentTree([0]*n,max,0,add,0,add)
    for r in range(n):
        dp.update(r,dp.sum(0,r))
        for l,a in R[r]:
            dp.add(l,r+1,a)
    print(dp.sum(0,n))
resolve()

Submission status: Time Limit Exceeded

Solution code:
# from https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2019/0106_educational_dp_4
import sys

class LazySegmentTree:
    def __init__(self,n):
        n2=1<<n.bit_length()
        self.n=n2
        self.offset=n2
        self.data=[0]*(n2<<1)
        self.lazy=[0]*(n2<<1)

        update_base=[0]*n
        propagate_indices=[[] for _ in [0]*n]
        update_indices=[[] for _ in [0]*n]
        for i in range(n):
            j=i+n2+1
            b=(j>>(-j&j).bit_length()-1)-1
            update_base[i]=b
            while b>1:
                b>>=1
                propagate_indices[i].append(b)
        for i in range(n):
            k=i+1
            while k:
                update_indices[i].append(update_base[k-1])
                k-=-k&k
        self.propagate_indices=propagate_indices
        self.update_indices=update_indices

    def _push(self,k):
        for i in reversed(self.propagate_indices[k]):
            v=self.lazy[i]
            if v==0:
                continue
            j=i<<1
            self.data[j]+=v
            self.data[j+1]+=v
            self.lazy[j]+=v
            self.lazy[j+1]+=v
            self.lazy[i]=0

    def add(self,k,x):
        for i in self.update_indices[k]:
            self.data[i]+=x
            self.lazy[i]+=x
        for i in self.propagate_indices[k]:
            self.data[i]=max(self.data[i*2],self.data[i*2+1])+self.lazy[i]

    def get(self,k):
        self._push(k)
        ret=max(map(self.data.__getitem__, self.update_indices[k]))
        i=k+self.offset+1
        self.data[i]+=ret
        tmp=self.data[i]
        while i>1:
            parent=i>>1
            sibling=i^1
            tmp=self.data[parent]=max(tmp, self.data[sibling])+self.lazy[parent]
            i=parent
        return ret




n,m=map(int,input().split())
range_ls=[0 for _ in [0]*n]
range_rs=[[] for _ in [0]*n]

for line in sys.stdin.readlines():
    l,r,a=map(int, line.split())
    range_ls[l-1]+=a
    range_rs[r-1].append((l-1,a))

lst=LazySegmentTree(n)
ans=0

for i, (la,rs) in enumerate(zip(range_ls,range_rs)):
    if la!=0:
        lst.add(i,la)
    ans=max(ans,lst.get(i))
    for l,a in rs:
        lst.add(l,-a)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,M = map(int,input().split())
LRA = [[int(x) for x in row.split()] for row in sys.stdin.readlines()]

R_to_LA = [[] for _ in range(N+1)]
for L,R,A in LRA:
    R_to_LA[R].append((L,A))

INF = 10 ** 18

size = 1<<18
data = [0] * (2*size)
lazy = [0] * (2*size)
left_end = [None] * (2*size)
right_end = [None] * (2*size)
q = [1]
left_end[1] = 0
right_end[1] = size
for n in range(1,size):
    L,R = left_end[n],right_end[n]
    M = (L+R)//2
    left_end[2*n] = L
    right_end[2*n] = M
    left_end[2*n+1] = M
    right_end[2*n+1] = R

def get_max(R):
    q = [1]
    ret = -INF
    while q:
        qq = []
        for i in q:
            iL = left_end[i]
            iR = right_end[i]
            if iR <= R:
                # 完全に含まれている
                x = data[i] + lazy[i]
                if ret < x:
                    ret = x
            elif R<=iL:
                # 完全に無関係
                pass
            else:
                # 部分的に交わっている
                j = i<<1; k = j+1
                lazy[j] += lazy[i]; lazy[k] += lazy[i]
                lazy[i] = 0
                qq.append(2*i); qq.append(2*i+1)
        q = qq
    return ret

def add(L,R,x):
    q = [1]
    q1 = []
    while q:
        qq = []
        for i in q:
            iL = left_end[i]
            iR = right_end[i]
            if L <= iL and iR <= R:
                # 完全に含まれている
                lazy[i] += x
            elif iR<=L or R<=iL:
                pass
            else:
                # 部分的に交わっている
                q1.append(i)
                j = i<<1; k = j+1
                lazy[j] += lazy[i]; lazy[k] += lazy[i]
                lazy[i] = 0
                qq.append(j)
                qq.append(k)
        q = qq
    for i in reversed(q1):
        j = i<<1; k = j+1
        data[i] = max(data[j]+lazy[j],data[k]+lazy[k])

for R in range(1,N+1):
    x = get_max(R)
    add(R,R+1,x)
    for L,A in R_to_LA[R]:
        add(L,R+1,A)

for n in range(size):
    lazy[2*n] += lazy[n]
    lazy[2*n+1] += lazy[n]

answer = max(lazy[size:])
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,M = map(int,input().split())
LRA = [[int(x) for x in input().split()] for _ in range(M)]

R_to_LA = [[] for _ in range(N+1)]
for L,R,A in LRA:
    R_to_LA[R].append((L,A))

INF = 10 ** 18

size = 1<<18
data = [0] * (2*size)
lazy = [0] * (2*size)
left_end = [None] * (2*size)
right_end = [None] * (2*size)
q = [1]
left_end[1] = 0
right_end[1] = size
for n in range(1,size):
    L,R = left_end[n],right_end[n]
    M = (L+R)//2
    left_end[2*n] = L
    right_end[2*n] = M
    left_end[2*n+1] = M
    right_end[2*n+1] = R

def get_max(L,R):
    q = [1]
    ret = -INF
    while q:
        qq = []
        for i in q:
            iL = left_end[i]
            iR = right_end[i]
            if L <= iL and iR <= R:
                # 完全に含まれている
                x = data[i] + lazy[i]
                if ret < x:
                    ret = x
            elif iR<=L or R<=iL:
                # 完全に無関係
                pass
            else:
                # 部分的に交わっている
                j = i<<1; k = j+1
                lazy[j] += lazy[i]; lazy[k] += lazy[i]
                lazy[i] = 0
                qq.append(2*i); qq.append(2*i+1)
        q = qq
    return ret

def add(L,R,x):
    q = [1]
    q1 = []
    while q:
        qq = []
        for i in q:
            iL = left_end[i]
            iR = right_end[i]
            if L <= iL and iR <= R:
                # 完全に含まれている
                lazy[i] += x
            elif iR<=L or R<=iL:
                pass
            else:
                # 部分的に交わっている
                q1.append(i)
                j = i<<1; k = j+1
                lazy[j] += lazy[i]; lazy[k] += lazy[i]
                lazy[i] = 0
                qq.append(j)
                qq.append(k)
        q = qq
    for i in reversed(q1):
        j = i<<1; k = j+1
        data[i] = max(data[j]+lazy[j],data[k]+lazy[k])

for R in range(1,N+1):
    x = get_max(0,R)
    add(R,R+1,x)
    for L,A in R_to_LA[R]:
        add(L,R+1,A)

for n in range(size):
    lazy[2*n] += lazy[n]
    lazy[2*n+1] += lazy[n]

answer = max(lazy[size:])
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,M = map(int,input().split())
LRA = [[int(x) for x in input().split()] for _ in range(M)]

R_to_LA = [[] for _ in range(N+1)]
for L,R,A in LRA:
    R_to_LA[R].append((L,A))

INF = 10 ** 18

size = 1<<18
data = [0] * (2*size)
lazy = [0] * (2*size)
left_end = [None] * (2*size)
right_end = [None] * (2*size)
q = [1]
left_end[1] = 0
right_end[1] = size
for n in range(1,size):
    L,R = left_end[n],right_end[n]
    M = (L+R)//2
    left_end[2*n] = L
    right_end[2*n] = M
    left_end[2*n+1] = M
    right_end[2*n+1] = R

def get_max(L,R):
    q = [1]
    ret = -INF
    while q:
        qq = []
        for i in q:
            iL = left_end[i]
            iR = right_end[i]
            if L <= iL and iR <= R:
                # 完全に含まれている
                x = data[i] + lazy[i]
                if ret < x:
                    ret = x
            elif iR<=L or R<=iL:
                # 完全に無関係
                pass
            else:
                # 部分的に交わっている
                j = i<<1; k = j+1
                lazy[j] += lazy[i]; lazy[k] += lazy[i]
                lazy[i] = 0
                qq.append(2*i); qq.append(2*i+1)
        q = qq
    return ret

def add(L,R,x,i=1):
    iL = left_end[i]
    iR = right_end[i]
    if L <= iL and iR <= R:
        # 完全に含まれている
        lazy[i] += x
        return data[i] + lazy[i]
    elif iR<=L or R<=iL:
        # 完全に無関係
        return data[i] + lazy[i]
    else:
        # 部分的に交わっている
        j = i<<1; k = j+1
        lazy[j] += lazy[i]; lazy[k] += lazy[i]
        lazy[i] = 0
        data[i] = max(add(L,R,x,j), add(L,R,x,k))
        return data[i]

for R in range(1,N+1):
    x = get_max(0,R)
    add(R,R+1,x)
    for L,A in R_to_LA[R]:
        add(L,R+1,A)

for n in range(size):
    lazy[2*n] += lazy[n]
    lazy[2*n+1] += lazy[n]

answer = max(lazy[size:])
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,M = map(int,input().split())
LRA = [[int(x) for x in input().split()] for _ in range(M)]

R_to_LA = [[] for _ in range(N+1)]
for L,R,A in LRA:
    R_to_LA[R].append((L,A))

INF = 10 ** 18

size = 1<<18
data = [0] * (2*size)
lazy = [0] * (2*size)
left_end = [None] * (2*size)
right_end = [None] * (2*size)
q = [1]
left_end[1] = 0
right_end[1] = size
while q:
    x = q.pop()
    L,R = left_end[x], right_end[x]
    M = (L+R)//2
    y = x<<1; z=y+1
    left_end[y] = L; right_end[y] = M
    left_end[z] = M; right_end[z] = R
    if y<size:
        q.append(y); q.append(z)

def get_max(L,R):
    q = [1]
    ret = -INF
    while q:
        i = q.pop()
        iL = left_end[i]
        iR = right_end[i]
        if L <= iL and iR <= R:
            # 完全に含まれている
            x = data[i] + lazy[i]
            if ret < x:
                ret = x
        elif iR<=L or R<=iL:
            # 完全に無関係
            pass
        else:
            # 部分的に交わっている
            j = i<<1; k = j+1
            lazy[j] += lazy[i]; lazy[k] += lazy[i]
            lazy[i] = 0
            q.append(2*i); q.append(2*i+1)
    return ret

def add(L,R,x,i=1):
    iL = left_end[i]
    iR = right_end[i]
    if L <= iL and iR <= R:
        # 完全に含まれている
        lazy[i] += x
        return data[i] + lazy[i]
    elif iR<=L or R<=iL:
        # 完全に無関係
        return data[i] + lazy[i]
    else:
        # 部分的に交わっている
        j = i<<1; k = j+1
        lazy[j] += lazy[i]; lazy[k] += lazy[i]
        lazy[i] = 0
        data[i] = max(add(L,R,x,j), add(L,R,x,k))
        return data[i]

for R in range(1,N+1):
    x = get_max(0,R)
    add(R,R+1,x)
    for L,A in R_to_LA[R]:
        add(L,R+1,A)

for n in range(size):
    lazy[2*n] += lazy[n]
    lazy[2*n+1] += lazy[n]

answer = max(lazy[size:])
print(answer)

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    def __init__(self, n):
        k = 1
        while k < n:
            k *= 2
        self.N = k
        self.node = [0] * (2 * self.N)
        self.ma = [0] * (2 * self.N)

    def _update(self, a, b, x, i, l, r):
        if l >= r:
            return
        if a <= l and r <= b:
            self.node[i] += x
            self.ma[i] += x
        elif l < b and a < r:
            mid = (l + r) // 2
            self._update(a, b, x, 2 * i + 1, l, mid)
            self._update(a, b, x, 2 * i + 2, mid, r)
            self.ma[i] = self.node[i] + max(self.ma[2 * i + 1], self.ma[2 * i + 2])

    def _find(self, a, b, i, l, r):
        if r <= a or b <= l:
            return -float("inf")
        if a <= l and r <= b:
            return self.ma[i]
        mid = (l + r) // 2
        return self.node[i] + max(self._find(a, b, 2 * i + 1, l, mid), self._find(a, b, 2 * i + 2, mid, r))

    def find(self, a, b):
        return self._find(a, b, 0, 0, self.N)

    def update(self, a, b, x):
        self._update(a, b, x, 0, 0, self.N)


N, M = map(int, input().split())
seg = SegmentTree(N)
d = {}
for i in range(M):
    l, r, x = map(int, input().split())
    l, r = l - 1, r - 1

    if r in d:
        d[r].append((l, x))
    else:
        d[r] = [(l, x)]

num = 0
tmp = 0
for i in range(N):
    if i > 0:
        tmp = seg.find(0, i)
    num = max(num, tmp)
    seg.update(i, i + 1, num)
    if i in d:
        for fir, sec in d[i]:
            seg.update(fir, i + 1, sec)

print(max(0, seg.find(0, N + 1)))