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: Accepted

Solution code:
import sys
import numpy as np
import numba
from numba import njit
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

A = np.array([1, 2, 3])

@njit((numba.types.optional(i8), ) * 2, cache=True)
def seg_f(x, y):
    if x is None:
        return y
    if y is None:
        return x
    return max(x, y)


@njit((i8, i8), cache=True)
def lazy_f(a, b):
    return a + b


@njit((i8, i8), cache=True)
def operate_f(x, a):
    return x + a


@njit((i8[:], i8[:], i8), cache=True)
def _eval_at(seg, lazy, i):
    return operate_f(seg[i], lazy[i])


@njit((i8[:], i8[:], i8), cache=True)
def _propagate_at(seg, lazy, i):
    seg[i] = _eval_at(seg, lazy, i)
    lazy[i << 1] = lazy_f(lazy[i << 1], lazy[i])
    lazy[i << 1 | 1] = lazy_f(lazy[i << 1 | 1], lazy[i])
    lazy[i] = 0


@njit((i8[:], ), cache=True)
def build(raw_data):
    N = len(raw_data)
    seg = np.empty(N + N, np.int64)
    seg[N:] = raw_data
    for i in range(N - 1, 0, -1):
        seg[i] = seg_f(seg[i << 1], seg[i << 1 | 1])
    return seg


@njit((i8[:], i8[:], i8), cache=True)
def _propagate_above(seg, lazy, i):
    H = 0
    while 1 << H <= i:
        H += 1
    for h in range(H - 1, 0, -1):
        _propagate_at(seg, lazy, i >> h)


@njit((i8[:], i8[:], i8), cache=True)
def _recalc_above(seg, lazy, i):
    while i > 1:
        i >>= 1
        seg[i] = seg_f(_eval_at(seg, lazy, i << 1),
                       _eval_at(seg, lazy, i << 1 | 1))


@njit((i8[:], i8[:], i8, i8), cache=True)
def set_val(seg, lazy, i, x):
    N = len(seg) // 2
    i += N
    _propagate_above(seg, lazy, i)
    seg[i], lazy[i] = x, 0
    _recalc_above(seg, lazy, i)


@njit((i8[:], i8[:], i8, i8), cache=True)
def fold(seg, lazy, l, r):
    N = len(seg) // 2
    l, r = l + N, r + N
    _propagate_above(seg, lazy, l // (l & -l))
    _propagate_above(seg, lazy, r // (r & -r) - 1)
    vl = vr = None
    while l < r:
        if l & 1:
            vl = seg_f(vl, _eval_at(seg, lazy, l))
            l += 1
        if r & 1:
            r -= 1
            vr = seg_f(_eval_at(seg, lazy, r), vr)
        l, r = l >> 1, r >> 1
    return seg_f(vl, vr)


@njit((i8[:], i8[:], i8, i8, i8), cache=True)
def operate_range(seg, lazy, l, r, x):
    N = len(seg) // 2
    l, r = l + N, r + N
    l0, r0 = l // (l & -l), r // (r & -r) - 1
    _propagate_above(seg, lazy, l0)
    _propagate_above(seg, lazy, r0)
    while l < r:
        if l & 1:
            lazy[l] = lazy_f(lazy[l], x)
            l += 1
        if r & 1:
            r -= 1
            lazy[r] = lazy_f(lazy[r], x)
        l, r = l >> 1, r >> 1
    _recalc_above(seg, lazy, l0)
    _recalc_above(seg, lazy, r0)

@njit((i8, i8[:]), cache=True)
def main(N, LRA):
    L, R, A = LRA[::3], LRA[1::3], LRA[2::3]
    ind = R.argsort()
    L, R, A = L[ind], R[ind], A[ind]
    seg = np.zeros((2 * N + 2), np.int64)
    lazy = np.zeros_like(seg)
    for r in range(1, N + 1):
        a, b = np.searchsorted(R, [r, r + 1])
        set_val(seg, lazy, r, fold(seg, lazy, 0, r))
        for i in range(a, b):
            operate_range(seg, lazy, L[i], r + 1, A[i])
    return fold(seg, lazy, 0, N + 1)

N, M = map(int, readline().split())
LRA = np.array(read().split(), np.int64)

print(main(N, LRA))

Submission status: Accepted

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


class LazySegmetTree:
    def __init__(self, size, op_data, u_data, op_lazy, u_lazy, op_merge):
        """
        size: 元の配列の長さ
        op_data, u_data: クエリ関数、単位元
        op_lazy, u_lazy: 遅延作用の関数、単位元
        op_merge: dataとlazyとの演算
        """
        self.N = size
        self.op_data = op_data
        self.op_lazy = op_lazy
        self.op_merge = op_merge
        self.u_data = u_data
        self.u_lazy = u_lazy
        #self.data = [u_data] * (2 * self.N)
        self.data = [0] * (2 * self.N)
        self.lazy = [u_lazy] * (2 * self.N)

    def initialize(self, arr):
        op = self.op_data
        for i, a in enumerate(arr, self.N):
            self.data[i] = a
        for i in reversed(range(1, self.N)):
            self.data[i] = op(self.data[i << 1], self.data[i << 1 | 1])

    def _propagate_top_down(self, L):
        op = self.op_lazy
        merge = self.op_merge
        unit = self.u_lazy
        for i in reversed(range(1, L.bit_length())):
            i = L >> i
            v = self.lazy[i]
            if v == unit:
                continue
            self.data[i] = merge(self.data[i], v)
            self.lazy[i << 1] = op(self.lazy[i << 1], v)
            self.lazy[i << 1 | 1] = op(self.lazy[i << 1 | 1], v)
            self.lazy[i] = unit

    def _propagate_bottom_up(self, i):
        merge = self.op_merge
        op = self.op_data
        while i > 1:
            i >>= 1
            self.data[i] = op(merge(self.data[i << 1], self.lazy[i << 1]),
                              merge(self.data[i << 1 | 1], self.lazy[i << 1 | 1]))

    def fold(self, L, R):
        res = self.u_data
        op = self.op_data
        merge = self.op_merge
        L += self.N
        R += self.N
        L0 = L // (L & -L)
        R0 = R // (R & -R) - 1
        self._propagate_top_down(L0)
        self._propagate_top_down(R0)
        while L < R:
            if L & 1:
                res = op(res, merge(self.data[L], self.lazy[L]))
                L += 1
            if R & 1:
                R -= 1
                res = op(res, merge(self.data[R], self.lazy[R]))
            L >>= 1
            R >>= 1
        return res

    def update(self, i, val):  # 未調整
        i += self.N
        i0 = i // (i & -i)
        self._propagate_top_down(i0)
        self.data[i] = self.op_merge(self.data[i], self.lazy[i])
        self.data[i] = self.op_data(val, self.data[i])
        self.lazy[i] = self.u_lazy
        self._propagate_bottom_up(i0)

    def range_update(self, L, R, val):
        op = self.op_lazy
        L += self.N
        R += self.N
        L0 = L // (L & -L)
        R0 = R // (R & -R) - 1
        self._propagate_top_down(L0)
        self._propagate_top_down(R0)
        while L < R:
            if L & 1:
                self.lazy[L] = op(val, self.lazy[L])
                L += 1
            if R & 1:
                R -= 1
                self.lazy[R] = op(val, self.lazy[R])
            L >>= 1
            R >>= 1
        self._propagate_bottom_up(L0)
        self._propagate_bottom_up(R0)


def main():
    N, M = map(int, input().split())
    LRA = list(tuple(map(int, input().split())) for _ in range(M))
    LRA.sort(key=lambda x: x[1])

    op_data = max
    unit_data = -10 ** 18
    op_lazy = add
    unit_lazy = 0
    op_merge = add
    seg = LazySegmetTree(N + 1, op_data, unit_data,
                         op_lazy, unit_lazy, op_merge)

    p = 0
    for i in range(N):
        val = seg.fold(0, i + 1)
        seg.update(i + 1, val)
        while p < M and LRA[p][1] <= i + 1:
            l, r, a = LRA[p]
            p += 1
            seg.range_update(l, r + 1, a)

    print(seg.fold(0, N + 1))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
interval=[[] for i in range(N)]
for i in range(M):
    l, r, a = map(int,input().split())
    interval[r-1].append((l-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] = max(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 = max(s, data[R-1])
        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

dp=[0]*N # dp[i] = max upto i. SegTree maintans max s.t. rightmost 1 is at i

for i in range(N):
    for j in range(len(interval[i])):
        l, a = interval[i][j]
        update(l, i+1, a)
    dp[i] = max(query(0, i+1), 0)
    update(i+1, i+2, dp[i]) # write "max up to i" at i+1 so that, in the next step, updates yields "max s.t. rightmost 1 is at i+1"

print(dp[-1])

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
interval=[[] for i in range(N)]
for i in range(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] = max(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 = max(s, data[R-1])
        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

dp=[0]*N

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

print(dp[0])

Submission status: Accepted

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: Accepted

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):
        # A : array of monoid (M, dot, unit)
        # (S, compose, identity) : sub monoid of End(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, self._logn, self._tree, self._lazy = n, logn, tree, [identity] * (2 * n)
        self._dot, self._unit, self._compose, self._identity, self._act = dot, unit, compose, identity, act

    def _ascend(self, i):
        tree, lazy, dot, act = self._tree, self._lazy, self._dot, self._act
        for _ in range(self._logn):
            i >>= 1
            tree[i] = act(lazy[i], dot(tree[i << 1], tree[i << 1 | 1]))

    def _descend(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

    # A[i] <- f(A[i]) for all i in [l, r)
    def range_act(self, l, r, f):
        l += self._n
        r += self._n
        # propagation isn't necessary if S is commutative
        # self._descend(l)
        # self._descend(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._ascend(l0)
        self._ascend(r0 - 1)

    # calculate product of A[l:r]
    def sum(self, l, r):
        l += self._n
        r += self._n
        self._descend(l)
        self._descend(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: Accepted

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):
        """
        A : array of monoid (M, dot, unit)
        (S, compose, identitiy) : sub monoid of End(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, self._logn, self._tree, self._lazy = n, logn, tree, [identity] * (2 * n)
        self._dot, self._unit, self._compose, self._identity, self._act = dot, unit, compose, identity, act

    def _ascend(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 _descend(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._descend(l)
        # self._descend(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._ascend(l0)
        self._ascend(r0 - 1)

    def sum(self, l, r):
        "calculate product of A[l:r]"
        l += self._n
        r += self._n
        self._descend(l)
        self._descend(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: Accepted

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

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, readline().split())
    queries = [[] for _ in range(n)]
    A = map(int, read().split())
    for l, r, a in zip(A, A, A):
        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: Accepted

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: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
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):
        l += self._n
        r += self._n
        # propagation isn't needed 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):
        l += self._n
        r += self._n
        self._propagate(l)
        self._propagate(r)
        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)

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=LazySegmentTree([0]*n,max,0,add,0,add)
    for r in range(n):
        dp.range_act(r,r+1,dp.sum(0,r))
        for l,a in R[r]:
            dp.range_act(l,r+1,a)
    print(dp.sum(0,n))
resolve()