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

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inl = lambda: [int(x) for x in sys.stdin.readline().split()]
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))


class LazySegTree:
    X_unit = 0
    A_unit = 0

    @classmethod
    def X_f(cls, x, y):
        return max(x, y)

    @classmethod
    def A_f(cls, x, y):
        return x + y

    @classmethod
    def operate(cls, x, a):
        return x + a

    def __init__(self, N):
        self.N = N
        self.X = [self.X_unit] * (N + N)
        self.A = [self.A_unit] * (N + N)

    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = x
        for i in range(self.N - 1, 0, -1):
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def _eval_at(self, i):
        return self.operate(self.X[i], self.A[i])

    def _propagate_at(self, i):
        self.X[i] = self._eval_at(i)
        self.A[i << 1] = self.A_f(self.A[i << 1], self.A[i])
        self.A[i << 1 | 1] = self.A_f(self.A[i << 1 | 1], self.A[i])
        self.A[i] = self.A_unit

    def _propagate_above(self, i):
        H = i.bit_length() - 1
        for h in range(H, 0, -1):
            self._propagate_at(i >> h)

    def _recalc_above(self, i):
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self._eval_at(i << 1), self._eval_at(i << 1 | 1))

    def __setitem__(self, i, x):
        i += self.N
        self._propagate_above(i)
        self.X[i] = x
        self.A[i] = self.A_unit
        self._recalc_above(i)

    def __getitem__(self, i):
        return self.fold(i, i + 1)

    def fold(self, L, R):
        L += self.N
        R += self.N
        self._propagate_above(L // (L & -L))
        self._propagate_above(R // (R & -R) - 1)
        vL = self.X_unit
        vR = self.X_unit
        while L < R:
            if L & 1:
                vL = self.X_f(vL, self._eval_at(L))
                L += 1
            if R & 1:
                R -= 1
                vR = self.X_f(self._eval_at(R), vR)
            L >>= 1
            R >>= 1
        return self.X_f(vL, vR)

    def operate_range(self, L, R, x):
        L += self.N
        R += self.N
        L0 = L // (L & -L)
        R0 = R // (R & -R) - 1
        self._propagate_above(L0)
        self._propagate_above(R0)
        while L < R:
            if L & 1:
                self.A[L] = self.A_f(self.A[L], x)
                L += 1
            if R & 1:
                R -= 1
                self.A[R] = self.A_f(self.A[R], x)
            L >>= 1
            R >>= 1
        self._recalc_above(L0)
        self._recalc_above(R0)


N, M = inl()
intervals = [None] * M
for i in range(M):
    l, r, a = inl()
    l -= 1
    r -= 1  # inclusive
    intervals[i] = (r, l, a)
intervals.sort()


def solve():
    st = LazySegTree(N)
    j = 0
    for i in range(N):
        pmax = st.fold(0, i)
        asum = 0
        while True:
            if j == len(intervals):
                break
            r, l, a = intervals[j]
            if r > i:
                break
            assert r == i
            asum += a
            st.operate_range(l, r, a)
            j += 1
        st.operate_range(i, i + 1, asum + pmax)
    return st.fold(0, N)


print(solve())

Submission status: Time Limit Exceeded

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

def solve():
    INF = float('inf')
    idEle = -INF
    def _binOpe(x, y):
        return x if x >= y else y
    def makeSegTreeLazy(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [idEle] * (2*numPow2)
        lazy = [0] * (2*numPow2)
        return data, lazy, numPow2
    def setInit(As):
        for iST, A in enumerate(As, numPow2):
            data[iST] = A
        for iST in reversed(range(1, numPow2)):
            data[iST] = _binOpe(data[2*iST], data[2*iST+1])
    def _update1(iST, A):
        vIfSet = _getVIfSet(iST, A)
        data[iST] += vIfSet
        lazy[iST] += A
    def _getVIfSet(iST, A):
        return A
    def _getIndices(iSt, iEn):
        iSTs = []
        L = iSt + numPow2
        R = iEn + numPow2
        L0 = L // (L & -L)
        R0 = R // (R & -R)
        while L < R:
            if L < L0:
                iSTs.append(L)
            if R < R0:
                iSTs.append(R)
            L >>= 1
            R >>= 1
        while L:
            iSTs.append(L)
            L >>= 1
        return iSTs
    def _propagate(iST):
        v = lazy[iST]
        if v:
            _update1(2*iST, v)
            _update1(2*iST+1, v)
            lazy[iST] = 0
    def update(iSt, iEn, A):
        iSTs = _getIndices(iSt, iEn)
        for iST in reversed(iSTs):
            _propagate(iST)
        L = iSt + numPow2
        R = iEn + numPow2
        while L < R:
            if L & 1:
                _update1(L, A)
                L += 1
            if R & 1:
                R -= 1
                _update1(R, A)
            L >>= 1
            R >>= 1
        for iST in iSTs:
            data[iST] = _binOpe(data[2*iST], data[2*iST+1])
    def getValue(iSt, iEn):
        iSTs = _getIndices(iSt, iEn)
        for iST in reversed(iSTs):
            _propagate(iST)
        ans = idEle
        L = iSt + numPow2
        R = iEn + numPow2
        while L < R:
            if L & 1:
                ans = _binOpe(ans, data[L])
                L += 1
            if R & 1:
                R -= 1
                ans = _binOpe(ans, data[R])
            L >>= 1
            R >>= 1
        return ans


    N, M = map(int, input().split())
    LRs = [[] for _ in range(N+1)]
    for _ in range(M):
        L, R, A = map(int, input().split())
        LRs[R].append((L, A))

    data, lazy, numPow2 = makeSegTreeLazy(N+1)
    setInit([0]*(N+1))

    for R in range(1, N+1):
        v = getValue(0, R)
        v0 = getValue(R, R+1)
        update(R, R+1, v-v0)
        for L, A in LRs[R]:
            update(L, R+1, A)

    ans = getValue(0, N+1)
    print(ans)


solve()

Submission status: Time Limit Exceeded

Solution code:
import itertools
import bisect
n, m = map(int, input().split())

q = []
for i in range(m):
    l, r, a = map(int, input().split())
    q.append([l - 1, r - 1, a])
q.sort()

left = []
for l, r, a in q:
    left.append(l)

left.append(float("inf"))

# dp = [None] * (n + 2)
# def dfs(i=-1):
#     if dp[i] is not None:
#         return dp[i]
#
#     if i == n:
#         dp[i] = 0
#         return dp[i]
#
#     dp[i] = max([dfs(j) + score(i + 1, j) for j in range(i + 1, n + 1)])
#     return dp[i]

t = 1
while t < (n + 1):
    t *= 2
seg = [0] * (t * 2 - 1)
lazy = [0] * len(seg)
up = lambda node: (node - 1) // 2
down = lambda node: [(node * 2) + 1, (node * 2) + 2]

def lazy_eval(node):
    if lazy[node]:
        value = lazy[node]
        lazy[node] = 0
        seg[node] += value

        if node < t - 1:
            children = down(node)
            lazy[children[0]] += value
            lazy[children[1]] += value
    return seg[node]

def add(x, l, r, node=0, sl=0, sr=t):
    if sr <= l or r <= sl:
        return

    if l <= sl and sr <= r:
        lazy[node] += x
        return

    sc = (sl + sr) // 2
    c = down(node)
    add(x, l, r, c[0], sl, sc)
    add(x, l, r, c[1], sc, sr)
    seg[node] = max(lazy_eval(c[0]), lazy_eval(c[1]))

prev = 0
score_table = [0] * (n + 1)
for i in reversed(range(-1, n)):
    left_start_index = bisect.bisect_left(left, i + 1)
    left_end_index = bisect.bisect_right(left, i + 1)
    for l, r, v in q[left_start_index: left_end_index]:
        add(v, i + 1, r + 1)
        
    add(prev, i + 1, i + 2)
    prev = lazy_eval(0)

print(prev)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()

class LazySegmentTree(object):
    def __init__(self, A, dot, unit, compose, identity, act):
        """
        (M, dot, unit) : monoid
        (S, compose, identitiy) : sub monoid of End(M)
        A : array of M
        compose : (f, g) -> fg (f, g in S)
        act : (f, x) -> f(x) (f in S, x in M)
        """
        logn = (len(A) - 1).bit_length()
        n = 1 << logn
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n = n
        self._logn = logn
        self._tree = tree
        self._lazy = [identity] * (2 * n)
        self._dot = dot
        self._unit = unit
        self._compose = compose
        self._identity = identity
        self._act = act

    def _fix_ancestors(self, i):
        tree, lazy, dot, act = self._tree, self._lazy, self._dot, self._act
        while i > 1:
            i >>= 1
            tree[i] = act(lazy[i], dot(tree[i << 1], tree[i << 1 | 1]))

    def _propagate(self, i):
        tree, lazy, identity, compose, act = self._tree, self._lazy, self._identity, self._compose, self._act
        for k in range(self._logn, 0, -1):
            p = i >> k
            f = lazy[p]
            tree[p << 1], lazy[p << 1] = act(f, tree[p << 1]), compose(f, lazy[p << 1])
            tree[p << 1 | 1], lazy[p << 1 | 1] = act(f, tree[p << 1 | 1]), compose(f, lazy[p << 1 | 1])
            lazy[p] = identity

    def range_act(self, l, r, f):
        "A[i] = f(A[i]) for all i in [l, r)"
        l += self._n
        r += self._n
        # propagation isn't necessary if S is commutative
        self._propagate(l)
        self._propagate(r - 1)
        l0, r0 = l, r
        tree, lazy, act, compose = self._tree, self._lazy, self._act, self._compose
        while l < r:
            if l & 1:
                tree[l], lazy[l] = act(f, tree[l]), compose(f, lazy[l])
                l += 1
            if r & 1:
                r -= 1
                tree[r], lazy[r] = act(f, tree[r]), compose(f, lazy[r])
            l >>= 1
            r >>= 1
        self._fix_ancestors(l0)
        self._fix_ancestors(r0 - 1)

    def sum(self, l, r):
        "calculate product of A[l:r]"
        l += self._n
        r += self._n
        self._propagate(l)
        self._propagate(r - 1)
        l_val = r_val = self._unit
        tree, dot = self._tree, self._dot
        while l < r:
            if l & 1:
                l_val = dot(l_val, tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = dot(tree[r], r_val)
            l >>= 1
            r >>= 1
        return dot(l_val, r_val)

from operator import add
def resolve():
    n, m = map(int, input().split())
    queries = [[] for _ in range(n)]
    for _ in range(m):
        l, r, a = map(int, input().split())
        queries[l - 1].append((r, a))

    # range max, range add
    tree = LazySegmentTree([0] * n, max, 0, add, 0, add)

    # dp[i][j] : i <= l の query を全て処理した後、j 番目に初めて 1 が現れるときの max score
    for i in range(n - 1, -1, -1):
        tree.range_act(i, i + 1, tree.sum(i, n)) # pointwise update
        for r, a in queries[i]:
            tree.range_act(i, r, a)

    print(max(0, tree.sum(0, n)))
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()

class LazySegmentTree(object):
    def __init__(self, A, dot, unit, compose, identity, act):
        """
        (M, dot, unit) : monoid
        (S, compose, identitiy) : sub monoid of End(M)
        A : array of M
        compose : (f, g) -> fg (f, g in S)
        act : (f, x) -> f(x) (f in S, x in M)
        """
        logn = (len(A) - 1).bit_length()
        n = 1 << logn
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n = n
        self._logn = logn
        self._tree = tree
        self._lazy = [identity] * (2 * n)
        self._dot = dot
        self._unit = unit
        self._compose = compose
        self._identity = identity
        self._act = act

    def _fix_ancestors(self, i):
        tree, lazy, dot, act = self._tree, self._lazy, self._dot, self._act
        while i > 1:
            i >>= 1
            tree[i] = act(lazy[i], dot(tree[i << 1], tree[i << 1 | 1]))

    def _propagate(self, i):
        tree, lazy, identity, compose, act = self._tree, self._lazy, self._identity, self._compose, self._act
        for k in range(self._logn, 0, -1):
            p = i >> k
            f = lazy[p]
            tree[p << 1], lazy[p << 1] = act(f, tree[p << 1]), compose(f, lazy[p << 1])
            tree[p << 1 | 1], lazy[p << 1 | 1] = act(f, tree[p << 1 | 1]), compose(f, lazy[p << 1 | 1])
            lazy[p] = identity

    def range_act(self, l, r, f):
        "A[i] = f(A[i]) for all i in [l, r)"
        l += self._n
        r += self._n
        # propagation isn't necessary if S is commutative
        # self._propagate(l)
        # self._propagate(r - 1)
        l0, r0 = l, r
        tree, lazy, act, compose = self._tree, self._lazy, self._act, self._compose
        while l < r:
            if l & 1:
                tree[l], lazy[l] = act(f, tree[l]), compose(f, lazy[l])
                l += 1
            if r & 1:
                r -= 1
                tree[r], lazy[r] = act(f, tree[r]), compose(f, lazy[r])
            l >>= 1
            r >>= 1
        self._fix_ancestors(l0)
        self._fix_ancestors(r0 - 1)

    def sum(self, l, r):
        "calculate product of A[l:r]"
        l += self._n
        r += self._n
        self._propagate(l)
        self._propagate(r - 1)
        l_val = r_val = self._unit
        tree, dot = self._tree, self._dot
        while l < r:
            if l & 1:
                l_val = dot(l_val, tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = dot(tree[r], r_val)
            l >>= 1
            r >>= 1
        return dot(l_val, r_val)

from operator import add
def resolve():
    n, m = map(int, input().split())
    queries = [None] * m
    for i in range(m):
        l, r, a = map(int, input().split())
        queries[i] = (l - 1, r, a)
    queries.sort()

    # range max, range add
    tree = LazySegmentTree([0] * n, max, 0, add, 0, add)

    # dp[i][j] : i <= l の query を全て処理した後、j 番目に初めて 1 が現れるときの max score
    for i in range(n - 1, -1, -1):
        tree.range_act(i, i + 1, tree.sum(i, n)) # pointwise update
        while queries and queries[-1][0] == i:
            l, r, a = queries.pop()
            tree.range_act(l, r, a)

    print(max(0, tree.sum(0, n)))
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()

class LazySegmentTree(object):
    def __init__(self, A, dot, unit, compose, identity, act):
        """
        (M, dot, unit) : monoid
        (S, compose, identitiy) : sub monoid of End(M)
        A : array of M
        compose : (f, g) -> fg (f, g in S)
        act : (f, x) -> f(x) (f in S, x in M)
        """
        logn = (len(A) - 1).bit_length()
        n = 1 << logn
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n = n
        self._logn = logn
        self._tree = tree
        self._lazy = [identity] * (2 * n)
        self._dot = dot
        self._unit = unit
        self._compose = compose
        self._identity = identity
        self._act = act

    def _fix_ancestors(self, i):
        tree, lazy, dot, act = self._tree, self._lazy, self._dot, self._act
        while i > 1:
            i >>= 1
            tree[i] = act(lazy[i], dot(tree[i << 1], tree[i << 1 | 1]))

    def _propagate(self, i):
        tree, lazy, identity, compose, act = self._tree, self._lazy, self._identity, self._compose, self._act
        for k in range(self._logn, 0, -1):
            p = i >> k
            f = lazy[p]
            tree[p << 1], lazy[p << 1] = act(f, tree[p << 1]), compose(f, lazy[p << 1])
            tree[p << 1 | 1], lazy[p << 1 | 1] = act(f, tree[p << 1 | 1]), compose(f, lazy[p << 1 | 1])
            lazy[p] = identity

    def range_act(self, l, r, f):
        "A[i] = f(A[i]) for all i in [l, r)"
        l += self._n
        r += self._n
        # propagation isn't necessary if S is commutative
        # self._propagate(l)
        # self._propagate(r - 1)
        l0, r0 = l, r
        tree, lazy, act, compose = self._tree, self._lazy, self._act, self._compose
        while l < r:
            if l & 1:
                tree[l], lazy[l] = act(f, tree[l]), compose(f, lazy[l])
                l += 1
            if r & 1:
                r -= 1
                tree[r], lazy[r] = act(f, tree[r]), compose(f, lazy[r])
            l >>= 1
            r >>= 1
        self._fix_ancestors(l0)
        self._fix_ancestors(r0 - 1)

    def sum(self, l, r):
        "calculate product of A[l:r]"
        l += self._n
        r += self._n
        self._propagate(l)
        self._propagate(r - 1)
        l_val = r_val = self._unit
        tree, dot = self._tree, self._dot
        while l < r:
            if l & 1:
                l_val = dot(l_val, tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = dot(tree[r], r_val)
            l >>= 1
            r >>= 1
        return dot(l_val, r_val)

from operator import add
def resolve():
    n, m = map(int, input().split())
    queries = [[] for _ in range(n)]
    for _ in range(m):
        l, r, a = map(int, input().split())
        queries[l - 1].append((r, a))

    # range max, range add
    tree = LazySegmentTree([0] * n, max, -INF, add, 0, add)

    # dp[i][j] : i <= l の query を全て処理した後、j 番目に初めて 1 が現れるときの max score
    for i in range(n - 1, -1, -1):
        tree.range_act(i, i + 1, tree.sum(i, n)) # pointwise update
        for r, a in queries[i]:
            tree.range_act(i, r, a)

    print(max(0, tree.sum(0, n)))
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()

class LazySegmentTree(object):
    def __init__(self, A, dot, unit, compose, identity, act):
        """
        (M, dot, unit) : monoid
        (S, compose, identitiy) : sub monoid of End(M)
        A : array of M
        compose : (f, g) -> fg (f, g in S)
        act : (f, x) -> f(x) (f in S, x in M)
        """
        logn = (len(A) - 1).bit_length()
        n = 1 << logn
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n = n
        self._logn = logn
        self._tree = tree
        self._lazy = [identity] * (2 * n)
        self._dot = dot
        self._unit = unit
        self._compose = compose
        self._identity = identity
        self._act = act

    def _fix_ancestors(self, i):
        tree, lazy, dot, act = self._tree, self._lazy, self._dot, self._act
        while i > 1:
            i >>= 1
            tree[i] = act(lazy[i], dot(tree[i << 1], tree[i << 1 | 1]))

    def _propagate(self, i):
        tree, lazy, identity, compose, act = self._tree, self._lazy, self._identity, self._compose, self._act
        for k in range(self._logn, 0, -1):
            p = i >> k
            f = lazy[p]
            tree[p << 1], lazy[p << 1] = act(f, tree[p << 1]), compose(f, lazy[p << 1])
            tree[p << 1 | 1], lazy[p << 1 | 1] = act(f, tree[p << 1 | 1]), compose(f, lazy[p << 1 | 1])
            lazy[p] = identity

    def range_act(self, l, r, f):
        "A[i] = f(A[i]) for all i in [l, r)"
        l += self._n
        r += self._n
        # propagation isn't necessary if S is commutative
        # self._propagate(l)
        # self._propagate(r - 1)
        l0, r0 = l, r
        tree, lazy, act, compose = self._tree, self._lazy, self._act, self._compose
        while l < r:
            if l & 1:
                tree[l], lazy[l] = act(f, tree[l]), compose(f, lazy[l])
                l += 1
            if r & 1:
                r -= 1
                tree[r], lazy[r] = act(f, tree[r]), compose(f, lazy[r])
            l >>= 1
            r >>= 1
        self._fix_ancestors(l0)
        self._fix_ancestors(r0 - 1)

    def sum(self, l, r):
        "calculate product of A[l:r]"
        l += self._n
        r += self._n
        self._propagate(l)
        self._propagate(r - 1)
        l_val = r_val = self._unit
        tree, dot = self._tree, self._dot
        while l < r:
            if l & 1:
                l_val = dot(l_val, tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = dot(tree[r], r_val)
            l >>= 1
            r >>= 1
        return dot(l_val, r_val)

from operator import add
def resolve():
    n, m = map(int, input().split())
    queries = [None] * m
    for i in range(m):
        l, r, a = map(int, input().split())
        queries[i] = (l - 1, r, a)
    queries.sort()

    # range max, range add
    tree = LazySegmentTree([0] * n, max, -INF, add, 0, add)

    # dp[i][j] : i <= l の query を全て処理した後、j 番目に初めて 1 が現れるときの max score
    for i in range(n - 1, -1, -1):
        tree.range_act(i, i + 1, tree.sum(i, n)) # pointwise update
        while queries and queries[-1][0] == i:
            l, r, a = queries.pop()
            tree.range_act(l, r, a)

    print(max(0, tree.sum(0, n)))
resolve()

Submission status: Time Limit Exceeded

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

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:
#!/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)
            
    la=[[]for _ in range(N+1)]
    
    for i in range(M):
        l,r,a=MI()
        la[r].append([l,a])
    
    
    #sst[i]はi桁目がビットの立っている最右である時のmax
    #lrのクエリはrまで来た時に，範囲内に加算
    
 
    for i in range(1,N+1):
        temp=sst.query(0,i)
        sst.add(i,i+1,temp)#とりあえず，[0,i)の最大値を入れておく
        
        for l,a in la[i]:
            sst.add(l,i+1,a)
        
            
    print(sst.query(0,N+1))

main()