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:
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)
    r = []
    while z:
        r.append(z)
        z >>= 1
    r.reverse()
    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 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)

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

# update[k, k+1)
def update1(k, x):
    #propagates(I[k])
    k += N0
    data[k-1] += x
    while k:
        k >>= 1
        data[k-1] = max(data[2*k-1], data[2*k]) + lazy[k-1]


# 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:
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)
    r = []
    while z:
        r.append(z)
        z >>= 1
    r.reverse()
    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 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)

    k = K[r]
    while k:
        data[k-1] = max(data[2*k-1], data[2*k])
        k >>= 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:
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 = []
for x in range(N0+1):
    y = N0 + x
    z = (y // (y & -y)) >> 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)

    for i in I[r]:
        data[i-1] = max(data[2*i-1], data[2*i])

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

    for i in I[k]:
        data[i-1] = max(data[2*i-1], data[2*i])

def query(r):
    return max(qquery(r))

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

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

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:
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 = []
for x in range(N0+1):
    y = N0 + x
    z = (y // (y & -y)) >> 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)

    for i in I[r]:
        data[i-1] = max(data[2*i-1], data[2*i])

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

    for i in I[k]:
        data[i-1] = max(data[2*i-1], data[2*i])

def query(r):
    return max(qquery(r))

def qquery(r):
    propagates(I[r])
    L = N0 + 0; R = N0 + r

    yield -INF
    while L < R:
        if R & 1:
            R -= 1
            yield data[R-1]
        if L & 1:
            yield data[L-1]
            L += 1
        L >>= 1; R >>= 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:
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-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

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

def query(l, r):
    return max(qquery(l, r))

def qquery(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    yield -INF
    while L < R:
        if R & 1:
            R -= 1
            yield data[R-1]
        if L & 1:
            yield data[L-1]
            L += 1
        L >>= 1; R >>= 1


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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,M = IL()
data = ILL(M)
R = [[] for i in range(N)]
for l,r,a in data:
  R[r-1].append([l-1,a])

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 = 0
  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

for r in range(N):
  update(r,r+1,query(0,r))
  for l,a in R[r]:
    update(l,r+1,-a)

print(-query(0,N+1))

Submission status: Accepted

Solution code:
class LazySegmentTree():
    def __init__(self,n,init,merge_func=min,ide_ele=10**18):
        self.n=(n-1).bit_length()
        self.merge_func=merge_func
        self.ide_ele=ide_ele
        self.data=[0 for i in range(1<<(self.n+1))]
        self.lazy=[0 for i in range(1<<(self.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):
        m=i.bit_length()-1
        for bit in range(m,0,-1):
            v=i>>bit
            add=self.lazy[v]
            self.lazy[v]=0
            self.data[2*v]+=add
            self.data[2*v+1]+=add
            self.lazy[2*v]+=add
            self.lazy[2*v+1]+=add

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

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

Submission status: Accepted

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<<(self.n+1))]
        self.lazy=[0 for i in range(1<<(self.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])

Submission status: Accepted

Solution code:
from collections import deque

class LazySegtree():
    def __init__(self,n,init_val,merge_func,ide_ele):
        self.n=n
        self.ide_ele=ide_ele
        self.merge_func=merge_func
        self.val=[0 for i in range(1<<n)]
        self.merge=[0 for i in range(1<<n)]
        self.parent=[-1 for i in range(1<<n)]
        self.lazy=[0 for i in range(1<<n)]
        deq=deque([1<<(n-1)])
        res=[]
        while deq:
            v=deq.popleft()
            res.append(v)
            if not v&1:
                gap=(v&-v)//2
                self.parent[v-gap]=v
                deq.append(v-gap)
                self.parent[v+gap]=v
                deq.append(v+gap)
        for v in res[::-1]:
            if v-1<len(init_val):
                self.val[v-1]=init_val[v-1]
            else:
                self.val[v-1]=10**18
            self.merge[v-1]=self.val[v-1]
            if not v&1:
                gap=(v&-v)//2
                self.merge[v-1]=self.merge_func(self.merge[v-1],self.merge[v-gap-1],self.merge[v+gap-1])

    def lower_kth_update(self,nd,k,x):
        if k==-1:
            return
        maxi=nd-(nd&-nd)+1+k
        ids=self.idgetter(nd,maxi)
        for pos in ids:
            gap=(pos&-pos)//2
            self.propagate(pos)
            if pos<=maxi:
                self.val[pos-1]+=x
                self.lazy[pos-gap-1]+=x*(gap!=0)

        if pos&1:
            self.merge[pos-1]=self.val[pos-1]
            ids.pop()
        ids=ids[::-1]
        for pos in ids:
            gap=(pos&-pos)//2
            self.merge[pos-1]=self.merge_func(self.val[pos-1],self.merge[pos-gap-1]+self.lazy[pos-gap-1],self.merge[pos+gap-1]+self.lazy[pos+gap-1])

    def upper_kth_update(self,nd,k,x):
        if k==-1:
            return
        mini=nd+(nd&-nd)-1-k
        ids=self.idgetter(nd,mini)
        for pos in ids:
            gap=(pos&-pos)//2
            self.propagate(pos)
            if pos>=mini:
                self.val[pos-1]+=x
                self.lazy[pos+gap-1]+=x*(gap!=0)

        if pos&1:
            self.merge[pos-1]=self.val[pos-1]
            ids.pop()
        ids=ids[::-1]
        for pos in ids:
            gap=(pos&-pos)//2
            self.merge[pos-1]=self.merge_func(self.val[pos-1],self.merge[pos-gap-1]+self.lazy[pos-gap-1],self.merge[pos+gap-1]+self.lazy[pos+gap-1])

    def update(self,l,r,x):
        pos=1<<(self.n-1)
        end=self.range_goal(l+1,r+1)
        ids=self.idgetter(pos,end)
        for pos in ids:
            self.propagate(pos)
        gap=(pos&-pos)//2
        self.val[pos-1]+=x
        self.upper_kth_update(pos-gap,pos-1-l-1,x)
        self.lower_kth_update(pos+gap,r-pos,x)

        if pos&1:
            self.merge[pos-1]=self.val[pos-1]
            ids.pop()
        for pos in ids[::-1]:
            gap=(pos&-pos)//2
            self.merge[pos-1]=self.merge_func(self.val[pos-1],self.merge[pos-gap-1]+self.lazy[pos-gap-1],self.merge[pos+gap-1]+self.lazy[pos+gap-1])

    def lower_kth_merge(self,nd,k,debug=False):
        res=self.ide_ele
        if k==-1:
            return res
        maxi=nd-(nd&-nd)+1+k
        ids=self.idgetter(nd,maxi)
        for pos in ids:
            self.propagate(pos)

        stack=[self.ide_ele]
        if pos&1:
            self.merge[pos-1]=self.val[pos-1]
            stack.append(self.merge[pos-1])
            ids.pop()
        for pos in ids[::-1]:
            gap=(pos&-pos)//2
            if pos<=maxi:
                self.merge[pos-1]=self.merge_func(self.val[pos-1],self.merge[pos-gap-1]+self.lazy[pos-gap-1])
                stack.append(self.merge[pos-1])
                self.merge[pos-1]=self.merge_func(self.merge[pos-1],self.merge[pos+gap-1]+self.lazy[pos+gap-1])
            else:
                self.merge[pos-1]=self.merge_func(self.val[pos-1],self.merge[pos-gap-1]+self.lazy[pos-gap-1],self.merge[pos+gap-1]+self.lazy[pos+gap-1])
        return self.merge_func(stack)

    def upper_kth_merge(self,nd,k):
        res=self.ide_ele
        if k==-1:
            return res
        mini=nd+(nd&-nd)-1-k
        ids=self.idgetter(nd,mini)
        for pos in ids:
            self.propagate(pos)

        stack=[self.ide_ele]
        if pos&1:
            self.merge[pos-1]=self.val[pos-1]
            stack.append(self.merge[pos-1])
            ids.pop()
        for pos in ids[::-1]:
            gap=(pos&-pos)//2
            if pos>=mini:
                self.merge[pos-1]=self.merge_func(self.val[pos-1],self.merge[pos+gap-1]+self.lazy[pos+gap-1])
                stack.append(self.merge[pos-1])
                self.merge[pos-1]=self.merge_func(self.merge[pos-1],self.merge[pos-gap-1]+self.lazy[pos-gap-1])
            else:
                self.merge[pos-1]=self.merge_func(self.val[pos-1],self.merge[pos-gap-1]+self.lazy[pos-gap-1],self.merge[pos+gap-1]+self.lazy[pos+gap-1])
        return self.merge_func(stack)

    def query(self,l,r):
        pos=1<<(self.n-1)
        end=self.range_goal(l+1,r+1)
        ids=self.idgetter(pos,end)
        for pos in ids:
            self.propagate(pos)
        gap=(pos&-pos)//2
        left=self.upper_kth_merge(pos-gap,pos-1-l-1)
        right=self.lower_kth_merge(pos+gap,r-pos)
        res=self.merge_func(left,right,self.val[pos-1])
        return res

    def propagate(self,pos):
        if self.lazy[pos-1]:
            self.val[pos-1]+=self.lazy[pos-1]
            self.merge[pos-1]+=self.lazy[pos-1]
            if not pos&1:
                gap=(pos&-pos)//2
                self.lazy[pos-gap-1]+=self.lazy[pos-1]
                self.lazy[pos+gap-1]+=self.lazy[pos-1]
            self.lazy[pos-1]=0
        return

    def idgetter(self,start,goal):
        res=[]
        pos=goal
        while pos!=start:
            res.append(pos)
            pos=self.parent[pos]
        res.append(start)
        return res[::-1]

    def range_goal(self,l,r):
        n=(l^r).bit_length()-1
        m=(l&-l).bit_length()-1
        if n>m:
            return (r>>n)<<n
        else:
            return l

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=LazySegtree(N.bit_length(),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,-a)
    Max[i]=max(-LST.query(0,N-1),0)
    if i:
        LST.update(i-1,i-1,-Max[i])

print(Max[0])

Submission status: Accepted

Solution code:

class StarrySkyTree:
    """ Starry Sky Tree(区間加算・区間最小(大)値取得) """

    def __init__(self, N, func, 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

def resolve():
    N, M = map(int, input().split())
    # 1_index
    Pair = [[] for _ in range(N+1)]
    for _ in range(M):
        l, r, a = map(int, input().split())
        Pair[r].append((l, a))

    seg = StarrySkyTree(N+1, func=max, intv=0)

    for i in range(1, N+1):
        _max = seg.query(0, i)
        seg.update(i, i+1, _max)
        for p in Pair[i]:
            l = p[0]
            a = p[1]
            seg.update(l, i+1, a)

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

if __name__ == "__main__":
    resolve()

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, seg[1])
        for i in range(a, b):
            operate_range(seg, lazy, L[i], r + 1, A[i])
    return seg[1]

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

print(main(N, LRA))