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: Wrong Answer

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
    seg[i] = x
    while i > 1:
        i >>= 1
        seg[i] = seg_f(seg[i << 1], seg[i << 1 | 1])


@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: Wrong Answer

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
#for l, a in interval[0]: 
#    if l == 0: dp[0] += a

for i in range(N):
    ith_sum = 0
    for j in range(len(interval[i])):
        l, a = interval[i][j]
        update(l, i, a)
        ith_sum += a
    dp[i] = max(query(0, i), ith_sum)
    update(i, i+1, dp[i])

print(max(dp))

Submission status: Wrong Answer

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
#for l, a in interval[0]: 
#    if l == 0: dp[0] += a

for i in range(N):
    ith_sum = 0
    for j in range(len(interval[i])):
        l, a = interval[i][j]
        update(l, i, a)
        ith_sum += a
    dp[i] = max(query(0, i), ith_sum)
    update(i, i+1, dp[i])

print(dp[-1])

Submission status: Wrong Answer

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)

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)

# left_start_index = len(left)
# while left_start_index:
#     target = left[left_start_index - 1]
#     left_end_index = left_start_index
#     left_start_index = bisect.bisect_left(left, target, 0, left_end_index)
#
#     # for l, r, v in q[left_start_index: left_end_index]:
#     #     print(l, r)
#     #     add(v, i + 1, r + 1)
#     # add(prev, i + 1, i + 2)
#     # prev = lazy_eval(0)
#
# print(prev)

left.append(float("inf"))
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(5, i + 1, r + 1)

    add(prev, i + 1, i + 2)
    prev = lazy_eval(0)

print(prev)

Submission status: Wrong Answer

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]:
        seg[0] += 1
        
    add(prev, i + 1, i + 2)
    prev = lazy_eval(0)

print(prev)

Submission status: Wrong Answer

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()
    
    import operator
    from functools import reduce
    class LazySegmentTree:
        def __init__(self, values, fn=max):
            """
            :param list values:
            :param callable fn:
            """
            # 単位元
            self._id = 0
            self._size = len(values)
            self._fn = fn

            tree = [self._id] * self._size * 2
            tree[self._size:] = values[:]
            for i in reversed(range(1, self._size)):
                tree[i] = fn(tree[i << 1], tree[i << 1 | 1])
            self._tree = tree
            self._delay = [self._id] * self._size * 2

        def _add(self, k, value):
            if k < self._size:
                self._delay[k] = self._delay[k] + value
            else:
                self._tree[k] = self._tree[k] + value

        def add(self, l, r, value):
            """
            :param int l:
            :param int r:
            :param value:
            """
            l += self._size
            r += self._size
            l0, r0 = l, r
            while l < r:
                if l & 1:
                    # 右側の子
                    self._add(l, value)
                    l += 1
                if r & 1:
                    # 左側の子
                    r -= 1
                    self._add(r, value)
                l >>= 1
                r >>= 1
            self._update(l0)
            self._update(r0)

        def _update(self, p):
            """
            self._tree[p] の親たちを最新化する
            :param int p:
            """
            p >>= 1
            while p > 0:
                self._tree[p] = self._fn(
                    self._tree[p << 1] + self._delay[p << 1],
                    self._tree[p << 1 | 1] + self._delay[p << 1 | 1]
                )
                p >>= 1

        def _eval(self, p):
            """
            self._tree[p] に遅延配列から値を移す
            :param int p:
            """
            # root から葉に向かって遅延配列を移していく
            for h in reversed(range(1, p.bit_length())):
                k = p >> h
                self._tree[k] = self._tree[k] + self._delay[k]
                self._add(k << 1, self._delay[k])
                self._add(k << 1 | 1, self._delay[k])
                self._delay[k] = self._id

        def get(self, l, r=None):
            """
            :param int l:
            :param int|None r:
            """
            if r is None:
                self._eval(self._size + l)
                return self._tree[self._size + l]
            ret_l = []
            ret_r = []
            l += self._size
            r += self._size
            self._eval(l)
            self._eval(r)
            while l < r:
                if l & 1:
                    ret_l.append(self._tree[l])
                    l += 1
                if r & 1:
                    r -= 1
                    ret_r.append(self._tree[r])
                l >>= 1
                r >>= 1
            return reduce(self._fn, ret_l + ret_r)

    sst = LazySegmentTree([0]*(N+3), fn=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.get(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)"""
        sst.get(0,N+2)
            
    print(sst.get(0,N+2))

main()

Submission status: Wrong Answer

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))
    if i>1:
        BIT_update(i-1,Max[i])
        BIT_update(i,-Max[i])

print(Max[1])

Submission status: Wrong Answer

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]=-query(0,N)
    if i>0:
        update(i-1,i,-Max[i])

print(Max[0])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
a = []
imos = [0] * (N + 1)
ls = [N] * (N + 1)
rs = [0] * (N + 1)


t = [[] for _ in range(N + 1)]
for _ in range(M):
  l, r, c = map(int, input().split())
  a.append((l, r, c))
  imos[l - 1] += c
  imos[r] -= c
  ls[r - 1] = min(ls[r - 1], l - 1)
  rs[l - 1] = max(rs[l - 1], r)

for i in range(N): rs[i + 1] = max(rs[i + 1], rs[i])
for i in range(N, 0, -1): ls[i - 1] = min(ls[i - 1], ls[i])

for i in range(N): imos[i + 1] += imos[i]
#print(ls, rs)
class SegTree:
  def segfunc(self, x, y):
    return max(x, y)
  def __init__(self, n, ide_ele, init_val):
    #####単位元######
    self.ide_ele = ide_ele
    #num:n以上の最小の2のべき乗
    self.num = 2 ** (n - 1).bit_length()
    self.seg = [self.ide_ele] * 2 * self.num
    #set_val
    for i in range(n):
      self.seg[i + self.num - 1] = init_val[i]    
    #built
    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
#print(a)
seg = SegTree(N + 1, 0, [0] * (N + 1))
for i in range(N + 1):
  q = seg.query(0, ls[i])
  seg.update(i, max(imos[i] + q, seg.query(ls[i], i)))
  #print(imos[i], q, seg.query(ls[i], i))
print(seg.query(0, N))

Submission status: Wrong Answer

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.n = n
        self.n0 = 2**(n-1).bit_length()
        self.e = e
        self.F = F
        self.lazy = [0]*(2*self.n0)
        self.data = [e]*(2*self.n0)

    def construct(self, a):
        for i, x in enumerate(a):
            self.data[i+self.n0] = x
        for i in range(self.n0-1, 0, -1):
            self.data[i] = self.F(self.data[2*i], self.data[2*i+1])

    def bottomup(self, i):
        i += self.n0
        k = i//(i & -i)
        c = k.bit_length()
        for j in range(c-1):
            k >>= 1
            self.data[k] = self.F(self.data[2*k], self.data[2*k+1]) + self.lazy[k]

    def topdown(self, i):
        i += self.n0
        k = i//(i & -i)
        c = k.bit_length()
        for j in range(c-1):
            idx = k >> (c - j - 1)
            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 query(self, l, r):
        self.topdown(l)
        self.topdown(r-1)
        L = l+self.n0
        R = r+self.n0

        s = -float("inf")
        while L < R:
            if R & 1:
                R -= 1
                s = self.F(s, self.data[R])
            if L & 1:
                s = self.F(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

        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.bottomup(l)
        self.bottomup(r-1)

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.add(0, j, a)
    tmp = seg.query(0, i)
    seg.add(i, i+1, tmp)
ans = seg.query(0, n+1)
print(ans)

Submission status: Wrong Answer

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

N0 = 2**((N+1).bit_length())
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):
    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 gindex(l, r):
        data[i-1] = max(data[2*i-1], data[2*i]) + lazy[i-1]

def update2(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = max(data[2*k+1], data[2*k+2])

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

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))

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

Submission status: Wrong Answer

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

N0 = 2**(N+1).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):
    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 gindex(l, r):
        data[i-1] = max(data[2*i-1], data[2*i]) + lazy[i-1]

def update2(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = max(data[2*k+1], data[2*k+2])

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

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))

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

Submission status: Wrong Answer

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):
    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 gindex(l, r):
        data[i-1] = max(data[2*i-1], data[2*i]) + lazy[i-1]

def update2(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = max(data[2*k+1], data[2*k+2])

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))

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

Submission status: Wrong Answer

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):
    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 gindex(l, r):
        data[i-1] = max(data[2*i-1], data[2*i]) + lazy[i-1]

def update2(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = max(data[2*k+1], data[2*k+2])

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])
    update2(i, query(0, i))
    for l, a in ys[i]:
        update(0, l, -a)
print(query(0,N+1))

Submission status: Wrong Answer

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(N):
    imos[:, i]+-imos[:, i-1]
dp = np.zeros(N, dtype = np.int64)
dp[0] = max(0, imos[0, 0])
for i in range(1, N):
    dp[i]=(dp[:i]+imos[:i, i]).max()
print(dp.max())