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:
#!/usr/bin/env pypy3
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,M=MI()

    class Lazysegtree:
        #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)
            
    sst=Lazysegtree([0]*(N+1), 0, True, max)
            
    lra=[[0,0,0]for _ in range(M)]
    lra.append([N+5,N+5,0])#番兵
    
    for i in range(M):
        lra[i][0],lra[i][1],lra[i][2]=MI()
        
    lra.sort(key=lambda x:x[1])
    
    
    #sst[i]はi桁目がビットの立っている最右である時のmax
    #lrのクエリはrまで来た時に，範囲内に加算
    
    now=0#クエリ処理用
    
    for i in range(1,N+1):
        temp=sst.query(0,i)
        #print(i,temp)
        sst.add(i,i+1,temp)#とりあえず，[0,i)の最大値を入れておく
        #print(sst.get(i,i+1))
        while i>=lra[now][1]:
            sst.add(lra[now][0],lra[now][1]+1,lra[now][2])
            #print(i,lra[now][0],lra[now][1]+1,lra[now][2])
            now+=1
        """L=[]
        for j in range(N+1):
            L.append(sst.get(j,j+1))
        print(L)"""
            
    print(sst.query(0,N+1))

main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy3
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,M=MI()
    
    class StarrySkyTree:
        """ Starry Sky Tree(区間加算・区間最小(大)値取得) """

        def __init__(self, N, func, intv):
            """
            N:要素数
            func:計算式(maxなど)
            intv:単位元
            """
            self.intv = intv
            self.func = func
            LV = (N-1).bit_length()
            self.N0 = 2**LV
            self.data = [0]*(2*self.N0)
            self.lazy = [0]*(2*self.N0)

        # 伝搬される区間のインデックス(1-indexed)を全て列挙するgenerator
        def gindex(self, l, r):
            L = l + self.N0; R = r + self.N0
            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):
            # 1-indexedで単調増加のインデックスリスト
            for i in reversed(ids):
                v = self.lazy[i-1]
                if not v:
                    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 update(self, l, r, x):
            """ 区間[l,r)の値にxを加算 """

            # 1. lazyの値は伝搬させない
            # 2. 区間[l,r)のdata, lazyの値を更新
            L = self.N0 + l; R = self.N0 + r
            while L < R:
                if R & 1:
                    R -= 1
                    self.lazy[R-1] += x; self.data[R-1] += x
                if L & 1:
                    self.lazy[L-1] += x; self.data[L-1] += x
                    L += 1
                L >>= 1; R >>= 1
            # 3. 更新される区間を部分的に含んだ区間のdataの値を更新 (lazyの値を考慮)
            for i in self.gindex(l, r):
                self.data[i-1] = self.func(self.data[2*i-1], self.data[2*i]) + self.lazy[i-1]

        def query(self, l, r):
            """ 区間[l,r)の最小(大)値を取得 """

            # 1. トップダウンにlazyの値を伝搬
            self.propagates(*self.gindex(l, r))
            L = self.N0 + l; R = self.N0 + r

            # 2. 区間[l, r)の最小(大)値を求める
            s = self.intv
            while L < R:
                if R & 1:
                    R -= 1
                    s = self.func(s, self.data[R-1])
                if L & 1:
                    s = self.func(s, self.data[L-1])
                    L += 1
                L >>= 1; R >>= 1
            return s

    inf=10**20
    sst = StarrySkyTree(N+1, max, -1*inf)
    lra=[[0,0,0]for _ in range(M)]
    lra.append([N+2,N+2,0])#番兵
    
    for i in range(M):
        lra[i][0],lra[i][1],lra[i][2]=MI()
        
    lra.sort(key=lambda x:x[1])
    
    
    #sst[i]はi桁目がビットの立っている最右である時のmax
    #lrのクエリはrまで来た時に，範囲内に加算
    sst.update(0,1,0)
    now=0#クエリ処理用
    
    for i in range(1,N+1):
        temp=sst.query(0,i)
        sst.update(i,i+1,temp)#とりあえず，[0,i)の最大値を入れておく
        while i>=lra[now][1]:
            sst.update(lra[now][0],lra[now][1]+1,lra[now][2])
            now+=1
            
    print(sst.query(0,N+1))

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

input=sys.stdin.readline

N,M=map(int,input().split())
interval=[[] for i in range(0,N)]
for i in range(0,M):
    l,r,a=map(int,input().split())
    interval[l-1].append((r-1,a))

# N: 処理する区間の長さ
INF = 10**30-1

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

def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1

# 遅延伝搬処理
def propagates(*ids):
    for i in reversed(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

# 区間[l, r)にxを加算
def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] += x; data[R-1] += x
        if L & 1:
            lazy[L-1] += x; data[L-1] += x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = min(data[2*i-1], data[2*i])

# 区間[l, r)内の最小値を求める
def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])
        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

Max=[0 for i in range(0,N)]
for i in range(N-1,-1,-1):
    for j in range(0,len(interval[i])):
        r,a=interval[i][j]
        update(i,r+1,-a)
    Max[i]=max(-query(0,N),0)
    if i>0:
        update(i-1,i,-Max[i])

print(Max[0])

Submission status: Time Limit Exceeded

Solution code:
import sys

input=sys.stdin.readline

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

#A1 ... AnのBIT(1-indexed)
n=N+1
BIT = [0]*(n+1)

#A1 ~ Aiまでの和 O(logN)
def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(idx,x):
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return

Max=[0 for i in range(0,N+2)]
for i in range(N,0,-1):
    for j in range(0,len(interval[i])):
        r,a=interval[i][j]
        BIT_update(i,a)
        BIT_update(r+1,-a)
    Max[i]=max(BIT_query(j) for j in range(1,N+1))
    Max[i]=max(Max[i],0)
    if i>1:
        BIT_update(i-1,Max[i])
        BIT_update(i,-Max[i])

print(Max[1])

Submission status: Time Limit Exceeded

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

class RAQ_RMQ():
    def __init__(self, n, F, e=float("inf")):
        self.n0 = 1<<(n-1).bit_length()
        self.e = e
        self.F = F
        self.data = [0]*(2*self.n0)
        self.lazy = [0]*(2*self.n0)

    def getIndex(self, l, r):
        l += self.n0; r += self.n0
        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 not v:
                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 update(self, l, r, x):
        *ids, = self.getIndex(l, r)

        l += self.n0; r += self.n0
        while l < r:
            if r & 1:
                r -= 1
                self.lazy[r-1] += x; self.data[r-1] += x
            if l & 1:
                self.lazy[l-1] += x; self.data[l-1] += x
                l += 1
            l >>= 1; r >>= 1
        for i in ids:
            self.data[i-1] = self.F(self.data[2*i-1], self.data[2*i]) + self.lazy[i-1]

    def query(self, l, r):
        self.propagates(*self.getIndex(l, r))
        l += self.n0; r += self.n0

        s = -float("inf")
        while l < r:
            if r & 1:
                r -= 1
                s = self.F(s, self.data[r-1])
            if l & 1:
                s = self.F(s, self.data[l-1])
                l += 1
            l >>= 1; r >>= 1
        return s

n,m = map(int, input().split())
memo = [[] for i in range(n+2)]
for i in range(m):
    l,r,a = map(int, input().split())
    memo[l].append((l,a))
    memo[r+1].append((l,-a))

seg = RAQ_RMQ(n+2, F=max, e=0)
for i in range(1, n+2):
    for j, a in memo[i]:
        seg.update(0, j, a)
    tmp = seg.query(0, i)
    seg.update(i, i+1, tmp)

ans = seg.query(0, n+1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

class RAQ_RMQ():
    def __init__(self, n, F=min, e=float("inf")):
        self.n0 = 1<<(n-1).bit_length()
        self.e = e
        self.F = F
        self.data = [0]*(2*self.n0)
        self.lazy = [0]*(2*self.n0)

    def getIndex(self, l, r):
        l += self.n0; r += self.n0
        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 not v:
                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 update(self, l, r, x):
        *ids, = self.getIndex(l, r)

        l += self.n0; r += self.n0
        while l < r:
            if r & 1:
                r -= 1
                self.lazy[r-1] += x; self.data[r-1] += x
            if l & 1:
                self.lazy[l-1] += x; self.data[l-1] += x
                l += 1
            l >>= 1; r >>= 1
        for i in ids:
            self.data[i-1] = self.F(self.data[2*i-1], self.data[2*i]) + self.lazy[i-1]

    def query(self, l, r):
        self.propagates(*self.getIndex(l, r))
        l += self.n0; r += self.n0

        s = self.e
        while l < r:
            if r & 1:
                r -= 1
                s = self.F(s, self.data[r-1])
            if l & 1:
                s = self.F(s, self.data[l-1])
                l += 1
            l >>= 1; r >>= 1
        return s

n,m = map(int, input().split())
memo = [[] for i in range(n+2)]
for i in range(m):
    l,r,a = map(int, input().split())
    memo[l].append((l,a))
    memo[r+1].append((l,-a))

seg = RAQ_RMQ(n+2, F=max, e=-float("inf"))
for i in range(1, n+2):
    for j, a in memo[i]:
        seg.update(0, j, a)
    tmp = seg.query(0, i)
    seg.update(i, i+1, tmp)
ans = seg.query(0, n+1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())

N0 = 2**N.bit_length()
LV = 2**N0
INF = 2**31-1
data = [0]*(2*N0)
lazy = [0]*(2*N0)

def gindex(l, r):
    L = l + N0; R = r + N0
    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(*ids):
    for i in reversed(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
        
def update(l, r, x):
    # 2. 区間[l, r)のdata, lazyの値を更新
    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] += x; data[R-1] += x
        if L & 1:
            lazy[L-1] += x; data[L-1] += x
            L += 1
        L >>= 1; R >>= 1

    # 3. 更新される区間を部分的に含んだ区間のdataの値を更新 (lazyの値を考慮)
    for i in gindex(l, r):
        data[i-1] = max(data[2*i-1], data[2*i]) + lazy[i-1]

def query(l, r):
    # 1. トップダウンにlazyの値を伝搬
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    # 2. 区間[l, r)の最小値を求める
    s = -INF
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[R-1])
        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

xs = [0]*(N+1)
ys = [[] for _ in range(N+1)]
for _ in range(M):
    l, r, a = map(int, input().split())
    xs[l] += a
    ys[r].append((l,a))

for i in range(1, N+1):
    #[0,i)にxs[i]を加算
    update(0,i,xs[i])
    update(i, i+1, query(0, i)-query(i,i+1))
    for l, a in ys[i]:
        update(0, l, -a)
print(query(0,N+1))

Submission status: Time Limit Exceeded

Solution code:
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res


import sys
input = sys.stdin.readline
#ss = SegTree([-1] * n, n, -1, max)
N, M = map(int, input().split())
xs = [0]*(N+1)
ys = [[] for _ in range(N+1)]
for _ in range(M):
    L, R, A = map(int, input().split())
    xs[L] += A
    ys[R].append((L,A))

dp = [0]*(N+1)
for i in range(1, N+1):
    for j in range(i):
        dp[j] += xs[i]
    dp[i] = max(dp[:i])
    for l, a in ys[i]:
        for j in range(l):
            dp[j] -= a
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

inf = 10 ** 16
n, m = MI()
rtol = defaultdict(list)
width = 1
while width < n + 1: width *= 2
dp = [0] * (width * 2 - 1)
lazy = [0] * (width * 2 - 1)
# bitのノードからsegのノードへの対応表を作る
btos = [0] * (width + 1)
sL = 0  # segの左端
bL = width  # bitの左端
while bL > 0:
    for bi, si in zip(range(bL, width + 1, bL * 2), range(sL, width * 2, 2)):
        btos[bi] = si
    bL //= 2
    sL = sL * 2 + 1
# print(btos)

def prop(node):
    value = lazy[node]
    if value == 0: return
    dp[node] += value
    if node < width - 1:
        lazy[node * 2 + 1] += value
        lazy[node * 2 + 2] += value
    lazy[node] = 0

def add_range(a, b, x, node=0, l=0, r=width):
    prop(node)
    if b <= l or r <= a: return
    if a <= l and r <= b:
        lazy[node] += x
        prop(node)
        return
    add_range(a, b, x, node * 2 + 1, l, (l + r) // 2)
    add_range(a, b, x, node * 2 + 2, (l + r) // 2, r)
    dp[node] = max(dp[node * 2 + 1], dp[node * 2 + 2])

# bitは葉からsegは根からの更新なので、stackにnodeをためてから処理する
def max_range(i):
    stack = []
    while i > 0:
        stack.append(btos[i])
        i -= i & -i
    res = -inf
    while stack:
        node = stack.pop()
        prop(node)
        tmp = dp[node]
        if tmp > res: res = tmp
    return res

def main():
    # 区間加算、区間最大がいるので、dpを遅延評価セグメント木にする
    for _ in range(m):
        l, r, a = MI()
        rtol[r].append([l, a])
    # print(rtol)
    # dp[i] iケタ目(1~)に最後の1があるときの最大スコア
    for i in range(1, n + 1):
        # まずi-1ケタ目までの最大値をdp[i]へ
        add_range(i, i + 1, max_range(i))
        # 右端（r）をiとする範囲について、
        # dp[j]のjが範囲に入るようであれば、
        # そのスコアを加算する
        for l, a in rtol[i]:
            add_range(l, i + 1, a)
        # print(dp)
    print(max_range(n + 1))

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

inf = 10 ** 16
n, m = MI()
rtol = defaultdict(list)
width = 1
while width < n + 1: width *= 2
dp = [0] * (width * 2 - 1)
lazy = [0] * (width * 2 - 1)

def prop(node, l, r):
    value = lazy[node]
    if value == 0: return
    dp[node] += value
    if r - l > 1:
        lazy[node * 2 + 1] += value
        lazy[node * 2 + 2] += value
    lazy[node] = 0

def add_range(a, b, x, node=0, l=0, r=width):
    prop(node, l, r)
    if b <= l or r <= a: return
    if a <= l and r <= b:
        lazy[node] += x
        prop(node, l, r)
        return
    add_range(a, b, x, node * 2 + 1, l, (l + r) // 2)
    add_range(a, b, x, node * 2 + 2, (l + r) // 2, r)
    dp[node] = max(dp[node * 2 + 1], dp[node * 2 + 2])

def max_range(a, b, node=0, l=0, r=width):
    if b <= l or r <= a: return -inf
    prop(node, l, r)
    if a <= l and r <= b: return dp[node]
    ret1 = max_range(a, b, node * 2 + 1, l, (l + r) // 2)
    ret2 = max_range(a, b, node * 2 + 2, (l + r) // 2, r)
    return max(ret1, ret2)

def main():
    # 区間加算、区間最大がいるので、dpを遅延評価セグメント木にする
    for _ in range(m):
        l, r, a = MI()
        rtol[r].append([l, a])
    # print(rtol)
    # dp[i] iケタ目(1~)に最後の1があるときの最大スコア
    for i in range(1, n + 1):
        # まずi-1ケタ目までの最大値をdp[i]へ
        add_range(i, i + 1, max_range(0, i))
        # 右端（r）をiとする範囲について、
        # dp[j]のjが範囲に入るようであれば、
        # そのスコアを加算する
        for l, a in rtol[i]:
            add_range(l, i + 1, a)
    print(max_range(0, n + 1))

main()

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)