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
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

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

INF = 10 ** 18

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

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

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

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

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

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

Submission status: Wrong Answer

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

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

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

INF = 10 ** 18

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

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

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

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

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

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

Submission status: Wrong Answer

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

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

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

INF = 10 ** 18

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
from itertools import accumulate, groupby

n,m = [int(i) for i in input().split()]
lra = [[int(i) for i in input().split()] for _ in range(m)] + [[n+1,n+1,0]]
compare_r = lambda x: x[1]
lra.sort(key = compare_r)

imos = [0]*(n+2)

left = [0]*(n+2) # l[i] = [0,i)に含まれる区間でdp
rprev = 0
c=0
for rr,gp in groupby(lra, compare_r):
    cc = left[rprev-1] + max(0,c)
#    print(c,cc,rprev,rr)
    for i in range(rprev,rr):
        left[i] = cc
    rprev = rr

    c=0
    for l,r,a in gp:
        l-=1
        imos[l] += a
        imos[r] -= a
        c+=a



imos = list(accumulate(imos))

dp = [0]*(n+1)
for i in range(n):
    dp[i] = imos[i] + left[i]


#print(sorted(lra, key=compare_r))
#print(imos)
#print(left)
#print(dp)
print(max(dp))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
from itertools import accumulate, groupby

n,m = [int(i) for i in input().split()]
lra = [[int(i) for i in input().split()] for _ in range(m)] + [[n+1,n+1,0]]
compare_r = lambda x: x[1]
lra.sort(key = compare_r)

imos = [0]*(n+2)

left = [0]*(n+2) # l[i] = [0,i)に含まれる区間でdp
rprev = 0
c=0
for rr,gp in groupby(lra, compare_r):
    for l,r,a in gp:
        l-=1
        imos[l] += a
        imos[r] -= a
        c+=a

    cc = left[rprev] + max(0,c)
    for i in range(rprev+1,rr+1):
        left[i] = cc
    rprev = rr

    c=0

imos = list(accumulate(imos))

dp = [0]*(n+1)
for i in range(n):
    dp[i] = imos[i] + left[i]


#print(sorted(lra, key=compare_r))
#print(imos)
#print(left)
#print(dp)
print(max(dp))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
from itertools import accumulate, groupby

n,m = [int(i) for i in input().split()]
lra = [[int(i) for i in input().split()] for _ in range(m)] + [[n+1,n+1,0]]
compare_r = lambda x: x[1]
lra.sort(key = compare_r)

imos = [0]*(n+2)

left = [0]*(n+2) # l[i] = iに真に含まれる区間でdp
rprev = 0
c=0
for rr,gp in groupby(lra, compare_r):
    cc = left[rprev-1] + max(0,c)
    for i in range(rprev,rr):
        left[i] = cc
    rprev = rr

    c=0
    for l,r,a in gp:
        l-=1
        imos[l] += a
        imos[r] -= a
        c+=a

imos = list(accumulate(imos))

dp = [0]*(n+1)
dp[0] = max(0,imos[0])
for i in range(1,n):
    dp[i] = imos[i] + left[i]


#print(sorted(lra, key=compare_r))
#print(imos)
#print(left)
#print(dp)
print(max(dp))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
from itertools import accumulate, groupby

n,m = [int(i) for i in input().split()]
lra = [[int(i) for i in input().split()] for _ in range(m)] + [[n+1,n+1,0]]
compare_r = lambda x: x[1]
lra.sort(key = compare_r)

imos = [0]*(n+2)

left = [0]*(n+1) # l[i] = iに真に含まれる区間でdp
rprev = 0
c=0
for rr,gp in groupby(lra, compare_r):
    cc = left[rprev-1] + max(0,c)
    for i in range(rprev,rr):
        left[i] = cc
    rprev = rr

    c=0
    for l,r,a in gp:
        l-=1
        imos[l] += a
        imos[r] -= a
        c+=a

imos = list(accumulate(imos))

dp = [0]*(n+1)
dp[0] = max(0,imos[0])
for i in range(1,n):
    dp[i] = imos[i] + left[i]


#print(sorted(lra))
#print(imos)
#print(left)
#print(dp)
print(max(dp))    




"""
for l,r,a in gp:
    l-=1
    imos[l] += a
    imos[r] -= a
    lpt = l
    if rpt != r:
        m = max(rpt,l)-1
        for i in range(max(rpt,l),r):
            left[i] = max(left[i], left[m] + c)
        rpt = r
        c=a
    else:
        c += a
m = rpt-1
print(rpt)
for i in range(rpt,n):
    left[i] = max(left[i], left[m] + c)


imos = list(accumulate(imos))

print(sorted(lra))
print(imos)
print(left)

dp = [0]*(n)
for i in range(n):
    x = imos[i] + left[i]
    dp[i] = max(dp[i], x, dp[i-1])

#print(dp)
print(dp[n-1])    
"""

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
from itertools import accumulate, groupby

n,m = [int(i) for i in input().split()]
lra = [[int(i) for i in input().split()] for _ in range(m)] + [[n+1,n+1,0]]
compare_r = lambda x: x[1]
lra.sort(key = compare_r)

imos = [0]*(n+2)

left = [0]*(n+1) # l[i] = iに真に含まれる区間でdp
rprev = 0
c=0
for rr,gp in groupby(lra, compare_r):
    cc = left[rprev-1] + max(0,c)
    for i in range(rprev,rr):
        left[i] = cc
    rprev = rr

    c=0
    for l,r,a in gp:
        l-=1
        imos[l] += a
        imos[r] -= a
        c+=a

imos = list(accumulate(imos))

#print(sorted(lra))
#print(imos)
#print(left)

dp = [0]*(n)
dp[0] = imos[0]
for i in range(1,n):
    dp[i] = max(dp[i], imos[i] + left[i], dp[i-1])

#print(dp)
print(dp[n-1])    




"""
for l,r,a in gp:
    l-=1
    imos[l] += a
    imos[r] -= a
    lpt = l
    if rpt != r:
        m = max(rpt,l)-1
        for i in range(max(rpt,l),r):
            left[i] = max(left[i], left[m] + c)
        rpt = r
        c=a
    else:
        c += a
m = rpt-1
print(rpt)
for i in range(rpt,n):
    left[i] = max(left[i], left[m] + c)


imos = list(accumulate(imos))

print(sorted(lra))
print(imos)
print(left)

dp = [0]*(n)
for i in range(n):
    x = imos[i] + left[i]
    dp[i] = max(dp[i], x, dp[i-1])

#print(dp)
print(dp[n-1])    
"""

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
from itertools import accumulate, groupby

n,m = [int(i) for i in input().split()]
lra = [[int(i) for i in input().split()] for _ in range(m)]
rrr = lambda x: x[1]
lra.sort(key = rrr)

imos = [0]*(n+1)

left = [0]*(n+1) # l[i] = i 以下に含まれる区間でのやつ

rprev = 0
c=0
for rr,gp in groupby(lra, rrr):
    cc = left[rprev]
    if c > 0:
        cc += c
    for i in range(rprev,rr):
        left[i] = max(left[i-1], cc)
    rprev = rr
    c=0
    for l,r,a in gp:
        l-=1
        imos[l] += a
        imos[r] -= a
        c+=a
rr = n
cc = left[rprev]
if c > 0:
    cc += c
for i in range(rprev,rr):
    left[i] = max(left[i-1], cc)



imos = list(accumulate(imos))

#print(sorted(lra))
#print(imos)
#print(left)

dp = [0]*(n)
dp[0] = imos[0]
for i in range(1,n):
    dp[i] = max(dp[i], imos[i] + left[i], dp[i-1])

#print(dp)
print(dp[n-1])    




"""
for l,r,a in gp:
    l-=1
    imos[l] += a
    imos[r] -= a
    lpt = l
    if rpt != r:
        m = max(rpt,l)-1
        for i in range(max(rpt,l),r):
            left[i] = max(left[i], left[m] + c)
        rpt = r
        c=a
    else:
        c += a
m = rpt-1
print(rpt)
for i in range(rpt,n):
    left[i] = max(left[i], left[m] + c)


imos = list(accumulate(imos))

print(sorted(lra))
print(imos)
print(left)

dp = [0]*(n)
for i in range(n):
    x = imos[i] + left[i]
    dp[i] = max(dp[i], x, dp[i-1])

#print(dp)
print(dp[n-1])    
"""

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
from itertools import accumulate, groupby

n,m = [int(i) for i in input().split()]
lra = [[int(i) for i in input().split()] for _ in range(m)]
rrr = lambda x: x[1]
lra.sort(key = rrr)

imos = [0]*(n+1)

left = [0]*(n) # l[i] = i 以下に含まれる区間でのやつ

rprev = 0
c=0
for rr,gp in groupby(lra, rrr):
    rr-=1
    cc = max(left[rprev-1], c + left[rprev])
    for i in range(rprev,rr):
        left[i] = cc
    rprev = rr
    c=0
    for l,r,a in gp:
        l-=1
        imos[l] += a
        imos[r] -= a
        c+=a
rr = n
cc = c + left[rprev]
if cc > 0:
    for i in range(rprev,rr):
        left[i] = cc



imos = list(accumulate(imos))

#print(sorted(lra))
#print(imos)
#print(left)

dp = [0]*(n)
dp[0] = imos[0]
for i in range(1,n):
    dp[i] = max(dp[i], imos[i] + left[i-1], dp[i-1])

#print(dp)
print(dp[n-1])    




"""
for l,r,a in gp:
    l-=1
    imos[l] += a
    imos[r] -= a
    lpt = l
    if rpt != r:
        m = max(rpt,l)-1
        for i in range(max(rpt,l),r):
            left[i] = max(left[i], left[m] + c)
        rpt = r
        c=a
    else:
        c += a
m = rpt-1
print(rpt)
for i in range(rpt,n):
    left[i] = max(left[i], left[m] + c)


imos = list(accumulate(imos))

print(sorted(lra))
print(imos)
print(left)

dp = [0]*(n)
for i in range(n):
    x = imos[i] + left[i]
    dp[i] = max(dp[i], x, dp[i-1])

#print(dp)
print(dp[n-1])    
"""

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
from itertools import accumulate

n,m = [int(i) for i in input().split()]
lra = [[int(i) for i in input().split()] for _ in range(m)]
lra.sort(key = lambda x: x[1])


imos = [0]*(n+1)
left = [0]*(n)

rpt = lra[0][1]
c=0
for l,r,a in lra:
    l-=1
    imos[l] += a
    imos[r] -= a
    lpt = l
    if rpt != r:
        for i in range(max(rpt,l),r):
            m = max(rpt,l)-1
            left[i] = max(left[i], left[m] + c)
        rpt = r
        c=a
    else:
        c += a


imos = list(accumulate(imos))

#print(sorted(lra))
#print(imos)
#print(left)

dp = [0]*(n)
for i in range(n):
    x = imos[i] + left[i]
    dp[i] = max(dp[i], x, dp[i-1])

#print(dp)
print(dp[n-1])

Submission status: Wrong Answer

Solution code:
import sys
from itertools import accumulate
from operator import itemgetter

N, M = map(int, input().split())
LRA = [tuple(map(int, sys.stdin.readline().split())) for _ in range(M)]

LRA.sort(key = itemgetter(1))
table = [0]*(N+1)

for _, r, a in LRA:
    table[r] += a
table2 = table[:]
for i in range(1, N+1):
    table[i] = max(table[i], table[i-1]) 
table = [t1 + t2 for t1, t2 in zip([0] + table, table2)]

dp = [0]*(N+1)
for l, r, a in LRA:
    dp[l] += a
    dp[r] -= a
dp = list(accumulate(dp))
print(max(dp[i] + table[i] for i in range(N+1)))

Submission status: Wrong Answer

Solution code:
import sys


class LazySegmentTree:
    """ [0, k) Add, [0, k) Max """

    # For speeding up index calculation, [data] [lazy] are implemented 1-rooted
    # but 'update' and 'get' query requires 0-indexed

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

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

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

    # [0, k)
    def add(self, k, x):
        # print('add', 'k:', k, 'x:', x, self.update_indices[k])
        for i in self.update_indices[k]:
            self.data[i] += x
            self.lazy[i] += x

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

    # [0, k)
    def get(self, k):
        self._push(k)

        # print('get', 'k:', k, self.update_indices[k])

        ret = max(map(self.data.__getitem__, self.update_indices[k]))
        # print('ret', ret)

        # This addition is specific for the problem.
        i = k + self.offset + 1
        self.data[i] += ret

        tmp = self.data[i]
        while i > 1:
            parent = i >> 1
            sibling = i ^ 1
            tmp = self.data[parent] = max(tmp, self.data[sibling]) + self.lazy[parent]
            i = parent

        return ret

    def _debug_print(self, data):
        a = 1
        while a <= self.offset:
            b = a << 1
            print('   ', data[a:b])
            a = b

    def debug_print(self):
        print('   data')
        self._debug_print(self.data)
        print('   lazy')
        self._debug_print(self.lazy)


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

lst = LazySegmentTree(n)

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

Submission status: Wrong Answer

Solution code:
import sys


class LazySegmentTree:
    """ [0, k) Add, [0, k) Max """

    # For speeding up index calculation, [data] [lazy] are implemented 1-rooted
    # but 'update' and 'get' query requires 0-indexed

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

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

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

    # [0, k)
    def add(self, k, x):
        # print('add', 'k:', k, 'x:', x, self.update_indices[k])
        for i in self.update_indices[k]:
            self.data[i] += x
            self.lazy[i] += x

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

    # [0, k)
    def get(self, k):
        self._push(k)

        ret = max(map(self.data.__getitem__, self.update_indices[k]))
        # print('ret', k, ret)

        i = k + self.offset + 1

        # This addition is specific for the problem.
        self.data[i] += ret

        tmp = self.data[i]
        while i > 1:
            parent = i >> 1
            sibling = i ^ 1
            tmp = self.data[parent] = max(tmp, self.data[sibling]) + self.lazy[parent]
            i = parent

        return ret

    def _debug_print(self, data):
        a = 1
        while a <= self.offset:
            b = a << 1
            print('   ', data[a:b])
            a = b

    def debug_print(self):
        print('   data')
        self._debug_print(self.data)
        print('   lazy')
        self._debug_print(self.lazy)


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

lst = LazySegmentTree(n)

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

Submission status: Wrong Answer

Solution code:
import sys


class LazySegmentTree:
    """ [0, k) Add, [0, k) Max """

    # For speeding up index calculation, [data] [lazy] are implemented 1-rooted
    # but 'update' and 'get' query requires 0-indexed

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

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

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

    # [0, k)
    def add(self, k, x):
        for i in self.update_indices[k]:
            self.data[i] += x
            self.lazy[i] += x

    # [0, k)
    def get(self, k):
        self._push(k)

        ret = max(map(self.data.__getitem__, self.update_indices[k]))
        # print('ret', k, ret)

        i = k + self.offset + 1
       
        # This addition is specific for the problem.
        self.data[i] += ret

        tmp = self.data[i]
        while i > 1:
            parent = i >> 1
            sibling = i ^ 1
            tmp = self.data[parent] = max(tmp, self.data[sibling]) + self.lazy[parent]
            i = parent

        return ret

    def _debug_print(self, data):
        a = 1
        while a <= self.offset:
            b = a << 1
            print('   ', data[a:b])
            a = b

    def debug_print(self):
        print('    data')
        self._debug_print(self.data)
        print('    lazy')
        self._debug_print(self.lazy)


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

lbt = LazySegmentTree(n)

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

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
L = [[] for i in range(N+1)]
R = [[] for i in range(N+1)]
for i in range(M):
    l, r, a = map(int, input().split())
    L[l-1].append((r, a))

INF = 2**31-1

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

I = []; K = []
for x in range(N0+1):
    y = N0 + x
    z = (y // (y & -y)) >> 1
    K.append(z >> 1)
    r = []
    while z:
        r.append(z)
        z >>= 1
    I.append(r)
I.append([])

J = []
for x in range(N0+1):
    y = N0 + x + 1
    z = (y // (y & -y)) - 1
    J.append(z-1 if z else 0)

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

# update [0, r)
def update(r, x):
    propagates(I[r])

    i = r
    while i:
        v = J[i-1]
        lazy[v] += x; data[v] += x
        i -= (i & -i)

    i = K[r]
    if i:
        data[i-1] = v = max(data[2*i-1], data[2*i])
        while i:
            v = data[i-1] = max(data[2*i-1], v)
            i >>= 1

# update[k, k+1)
def update1(k, x):
    propagates(I[k])
    k += N0 - 1
    data[k] += x

    while k:
        k = (k - 1) >> 1
        data[k] = max(data[2*k+1], data[2*k+2])


# query [0, r)
def query(r):
    return max(map(data.__getitem__, qquery(r)))

def qquery(r):
    propagates(I[r])

    while r:
        yield J[r-1]
        r -= (r & -r)

# query [k, k+1)
def query1(k, x):
    propagates(I[k])
    return data[k + N0 - 1]


for i in range(N):
    for r, a in L[i]:
        update(i+1, a)
        R[r].append((i, a))
    for l, a in R[i]:
        update(l+1, -a)
    v = query(i+1)
    update1(i+1, v)
for l, a in R[N]:
    update(l+1, -a)
print(query(N+1))

Submission status: Time Limit Exceeded

Solution code:

class LazySegmentTree():
    def __init__(self,n,init,merge_func,ide_ele):
        self.n=(n-1).bit_length()
        self.merge_func=merge_func
        self.ide_ele=ide_ele
        self.data=[0 for i in range(1<<(n+1))]
        self.lazy=[0 for i in range(1<<(n+1))]
        for i in range(n):
            self.data[2**self.n+i]=init[i]
        for i in range(2**self.n-1,0,-1):
            self.data[i]=self.merge_func(self.data[2*i],self.data[2*i+1])

    def propagate_above(self,i):
        ids=[]
        while i:
            i>>=1
            ids.append(i)
        for v in ids[::-1]:
            self.data[v]+=self.lazy[v]
            self.lazy[2*v]+=self.lazy[v]
            self.lazy[2*v+1]+=self.lazy[v]
            self.lazy[v]=0

    def remerge_above(self,i):
        ids=[]
        while i:
            i>>=1
            self.data[i]=self.merge_func(self.data[2*i]+self.lazy[2*i],self.data[2*i+1]+self.lazy[2*i+1])

    def update(self,l,r,x):
        l+=1<<self.n
        r+=1<<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.lazy[l]+=x
                l+=1
            if r&1:
                self.lazy[r-1]+=x
            l>>=1
            r>>=1
        self.remerge_above(l0)
        self.remerge_above(r0)

    def query(self,l,r):
        l+=1<<self.n
        r+=1<<self.n
        l0=l//(l&-l)
        r0=r//(r&-r)-1
        self.propagate_above(l0)
        self.propagate_above(r0)
        res=self.ide_ele
        while l<r:
            if l&1:
                res=self.merge_func(res,self.data[l]+self.lazy[l])
                l+=1
            if r&1:
                res=self.merge_func(res,self.data[r-1]+self.lazy[r-1])
            l>>=1
            r>>=1
        return res

import sys

input=sys.stdin.readline

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

init=[0]*N
LST=LazySegmentTree(N,init,merge_func=min,ide_ele=10**18)

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

print(Max[0])