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:
class RMQ:
    def __init__(self, n):
        k = 1
        while k < n:
            k *= 2
        self.N = k
        self.node = [0] * (2 * self.N)
        self.ma = [0] * (2 * self.N)

    def _update(self, a, b, x, i, l, r):
        if l >= r:
            return
        if a <= l and r <= b:
            self.node[i] += x
            self.ma[i] += x
        elif l < b and a < r:
            mid = (l + r) // 2
            self._update(a, b, x, 2 * i, l, mid)
            self._update(a, b, x, 2 * i + 1, mid, r)
            self.ma[i] = self.node[i] + max(self.ma[2 * i], self.ma[2 * i + 1])

    def _find(self, a, b, i, l, r):
        if r <= a or b <= l:
            return -float("inf")
        if a <= l and r <= b:
            return self.ma[i]
        mid = (l + r) // 2
        return self.node[i] + max(self._find(a, b, 2 * i, l, mid), self._find(a, b, 2 * i + 1, mid, r))

    def find(self, a, b):
        return self._find(a, b, 1, 0, self.N)

    def update(self, a, b, x):
        self._update(a, b, x, 1, 0, self.N)


N, M = map(int, input().split())
rmq = RMQ(N)
a = {}
d = {}
for i in range(M):
    l, r, x = map(int, input().split())
    if l in a:
        a[l].append(x)
    else:
        a[l] = [x]

    if r in d:
        d[r].append((l, x))
    else:
        d[r] = [(l, x)]

ans = 0

for i in range(1, N + 1):
    if i in a:
        for a1 in a[i]:
            rmq.update(0, i, a1)
    tmp = rmq.find(0, i)
    ans = max(ans, tmp)
    rmq.update(i, i + 1, tmp)
    if i in d:
        for fir, sec in d[i]:
            rmq.update(0, fir, -sec)

print(ans)

Submission status: Time Limit Exceeded

Solution code:


class SegmentTreeLazy:
    def __init__(self, n):
        self.N = n
        self.tree = [0 for _ in range(self.N * 4)]
        self.lazy = [0 for _ in range(self.N * 4)]

    def __push(self, node):
        if self.lazy[node]:
            lz = self.lazy[node]
            lchild = (node << 1) + 1
            rchild = lchild + 1

            self.lazy[lchild] += lz
            self.tree[lchild] += lz
            self.lazy[rchild] += lz
            self.tree[rchild] += lz
            self.lazy[node] = 0

    def update(self, node, left, right, a, b, val):
        if a > right or b < left:
            return

        if a <= left and right <= b:
            self.lazy[node] += val
            self.tree[node] += val
            return

        mid = (left + right) >> 1
        lchild = (node << 1) + 1
        rchild = lchild + 1

        self.__push(node)

        self.update(lchild, left, mid, a, b, val)
        self.update(rchild, mid + 1, right, a, b, val)
        self.tree[node] = max(self.tree[lchild], self.tree[rchild])


n, m = map(int, raw_input().split())
events = []
for _ in range(m):
    l, r, v = map(int, raw_input().split())
    events.append((l    , 0,  v, l, r))
    events.append((r + 1, 1, -v, l, r))
events.sort()

tree = SegmentTreeLazy(n + 1)
ind = 0
resp = 0
activos = 0
for i in range(1, n + 1):
    while ind < len(events) and events[ind][0] == i:
        t, k, v, l, r = events[ind]
        activos += v
        if k == 1:
            tree.update(0, 0, n - 1, l, r, -v)
        ind += 1

    best = tree.tree[0]
    resp = max(resp, activos + best)
    tree.update(0, 0, n - 1, i, i, best)
print(resp)

Submission status: Time Limit Exceeded

Solution code:


class SegmentTreeLazy:
    def __init__(self, n):
        self.N = n
        self.tree = [0 for _ in range(self.N * 4)]
        self.lazy = [0 for _ in range(self.N * 4)]

    def __left_node(self, node):
        return (node << 1) + 1

    def __right_node(self, node):
        return (node << 1) + 2

    def __push(self, node):
        if self.lazy[node]:
            lchild = self.__left_node(node)
            rchild = self.__right_node(node)

            self.lazy[lchild] += self.lazy[node]
            self.tree[lchild] += self.lazy[node]
            self.lazy[rchild] += self.lazy[node]
            self.tree[rchild] += self.lazy[node]
            self.lazy[node] = 0

    def update(self, a, b, val):
        self.__update(0, 0, self.N - 1, a, b, val)

    def __update(self, node, left, right, a, b, val):
        if a > right or b < left:
            return

        if a <= left and right <= b:
            self.lazy[node] += val
            self.tree[node] += val
            return

        mid = (left + right) >> 1
        lchild = self.__left_node(node)
        rchild = self.__right_node(node)

        self.__push(node)

        self.__update(lchild, left, mid, a, b, val)
        self.__update(rchild, mid + 1, right, a, b, val)
        self.tree[node] = max(self.tree[lchild], self.tree[rchild])

    def query(self, a, b):
        return self.__query(0, 0, self.N - 1, a, b)

    def __query(self, node, left, right, a, b):
        if a > right or b < left:
            return 0

        if a <= left and right <= b:
            return self.tree[node]

        mid = (left + right) >> 1
        lchild = self.__left_node(node)
        rchild = self.__right_node(node)

        self.__push(node)

        left_child = self.__query(lchild, left, mid, a, b)
        right_child = self.__query(rchild, mid + 1, right, a, b)

        return max(left_child, right_child)


n, m = map(int, raw_input().split())
events = []
for _ in range(m):
    l, r, v = map(int, raw_input().split())
    events.append((l    , 0,  v, l, r))
    events.append((r + 1, 1, -v, l, r))
events.sort()

tree = SegmentTreeLazy(n + 1)
ind = 0
resp = 0
activos = 0
for i in range(1, n + 1):
    while ind < len(events) and events[ind][0] == i:
        t, k, v, l, r = events[ind]
        activos += v
        if k == 1:
            tree.update(l, r, -v)
        ind += 1

    best = tree.query(0, i)
    resp = max(resp, activos + best)
    tree.update(i, i, best)
print(resp)

Submission status: Time Limit Exceeded

Solution code:


class SegmentTreeLazy:
    def __init__(self, n):
        self.N = n
        self.tree = [0 for _ in range(self.N * 4)]
        self.lazy = [0 for _ in range(self.N * 4)]

    def __left_node(self, node):
        return (node << 1) + 1

    def __right_node(self, node):
        return (node << 1) + 2

    def __push(self, node):
        if self.lazy[node]:
            lchild = self.__left_node(node)
            rchild = self.__right_node(node)

            self.lazy[lchild] += self.lazy[node]
            self.tree[lchild] += self.lazy[node]
            self.lazy[rchild] += self.lazy[node]
            self.tree[rchild] += self.lazy[node]
            self.lazy[node] = 0

    def update(self, a, b, val):
        self.__update(0, 0, self.N - 1, a, b, val)

    def __update(self, node, left, right, a, b, val):
        if a > right or b < left:
            return

        if a <= left and right <= b:
            self.lazy[node] += val
            self.tree[node] += val
            return

        mid = (left + right) >> 1
        lchild = self.__left_node(node)
        rchild = self.__right_node(node)

        self.__push(node)

        self.__update(lchild, left, mid, a, b, val)
        self.__update(rchild, mid + 1, right, a, b, val)
        self.tree[node] = max(self.tree[lchild], self.tree[rchild])

    def query(self, a, b):
        return self.__query(0, 0, self.N - 1, a, b)

    def __query(self, node, left, right, a, b):
        if a > right or b < left:
            return 0

        if a <= left and right <= b:
            return self.tree[node]

        mid = (left + right) >> 1
        lchild = self.__left_node(node)
        rchild = self.__right_node(node)

        self.__push(node)

        left_child = self.__query(lchild, left, mid, a, b)
        right_child = self.__query(rchild, mid + 1, right, a, b)

        return max(left_child, right_child)


n, m = map(int, raw_input().split())
events = []
for _ in range(m):
    l, r, v = map(int, raw_input().split())
    events.append((l    , 0,  v, l, r))
    events.append((r + 1, 1, -v, l, r))
events.sort()

tree = SegmentTreeLazy(n + 1)
ind = 0
resp = 0
activos = 0
for i in range(1, n + 1):
    while ind < len(events):
        t, k, v, l, r = events[ind]
        if i < t:
            break
        activos += v
        if k == 1:
            tree.update(l, r, -v)
        ind += 1

    best = tree.query(0, i)
    resp = max(resp, activos + best)
    tree.update(i, i, best)
print(resp)

Submission status: Time Limit Exceeded

Solution code:
class StarrySkyTree:
    def __init__(self,num,default,func):
        leaf=1<<(num-1).bit_length()
        self.leaf=leaf
        self.d=default
        self.data=[default]*leaf*2
        self.lazy=[0]*leaf*2
        self.f=func
    def merge(self,a,b):
        return self.f(a,b)
    def indices(self,l,r):
        L,R=l+self.leaf,r+self.leaf
        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 zeroindices(self,k):
        K=k+self.leaf
        limit=(K//(K&-K))>>1
        while K:
            if K<=limit:
                yield K
            K>>=1
    def _propagates(self,*ids):
        for i in reversed(ids):
            v=self.lazy[i-1]
            if v==0:
                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 add(self,l,r,x):
        L,R=l+self.leaf,r+self.leaf
        while L<R:
            if L&1:
                self.lazy[L-1]+=x; self.data[L-1]+=x
                L+=1
            if R&1:
                R-=1
                self.lazy[R-1]+=x; self.data[R-1]+=x
            L>>=1; R>>=1
        for i in self.indices(l,r):
            self.data[i-1]=self.merge(self.data[2*i-1],self.data[2*i])+self.lazy[i-1]
    def add1(self,k,x):
        k+=self.leaf
        self.data[k-1]+=x
        while k:
            k>>=1
            self.data[k-1]=self.merge(self.data[2*k-1],self.data[2*k])+self.lazy[k-1]
    def query0(self,k):
        self._propagates(*self.zeroindices(k))
        L,R=self.leaf,k+self.leaf
        ret=0
        while L<R:
            if L&1:
                ret=self.merge(ret,self.data[L-1])
                L+=1
            if R&1:
                R-=1
                ret=self.merge(ret,self.data[R-1])
            L>>=1; R>>=1
        return ret

import sys
input=sys.stdin.readline
n,m=map(int,input().split())

def f(a,b):
    return max(a,b)

sst=StarrySkyTree(n+1,0,f)
R=[[] for _ in range(n+1)]
for _ in range(m):
    l,r,a=map(int,input().split())
    R[r].append((l,a))
for i in range(1,n+1):
    v=sst.query0(i)
    sst.add1(i,v)
    for l,a in R[i]:
        sst.add(l,i+1,a)
print(sst.query0(n+1))

Submission status: Time Limit Exceeded

Solution code:
class StarrySkyTree:
    def __init__(self,param,default,func):
        if isinstance(param,list):
            num=len(param)
        else:
            num=param
        leaf=1<<(num-1).bit_length()
        self.leaf=leaf
        self.d=default
        if isinstance(param,list):
            self.data=[default]*(leaf-1)+param+[default]*(leaf-num+1)
            for i in range(self.leaf-2,-1,-1):
                self.data[i]=func(self.data[i*2],self.data[i*2+1])
        else:
            self.data=[default]*leaf*2
        self.lazy=[0]*leaf*2
        self.f=func
    def merge(self,a,b):
        return self.f(a,b)
    def indices(self,l,r):
        L,R=l+self.leaf,r+self.leaf
        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 zeroindices(self,k):
        K=k+self.leaf
        limit=(K//(K&-K))>>1
        while K:
            if K<=limit:
                yield K
            K>>=1
    def _propagates(self,*ids):
        for i in reversed(ids):
            v=self.lazy[i-1]
            if v==0:
                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 add(self,l,r,x):
        L,R=l+self.leaf,r+self.leaf
        while L<R:
            if L&1:
                self.lazy[L-1]+=x; self.data[L-1]+=x
                L+=1
            if R&1:
                R-=1
                self.lazy[R-1]+=x; self.data[R-1]+=x
            L>>=1; R>>=1
        for i in self.indices(l,r):
            self.data[i-1]=self.merge(self.data[2*i-1],self.data[2*i])+self.lazy[i-1]
    def add1(self,k,x):
        k+=self.leaf
        self.data[k-1]+=x
        while k:
            k>>=1
            self.data[k-1]=self.merge(self.data[2*k-1],self.data[2*k])+self.lazy[k-1]
    def query0(self,k):
        self._propagates(*self.zeroindices(k))
        L,R=self.leaf,k+self.leaf
        ret=0
        while L<R:
            if L&1:
                ret=self.merge(ret,self.data[L-1])
                L+=1
            if R&1:
                R-=1
                ret=self.merge(ret,self.data[R-1])
            L>>=1; R>>=1
        return ret

import sys
input=sys.stdin.readline
n,m=map(int,input().split())

def f(a,b):
    return max(a,b)

sst=StarrySkyTree(n+1,0,f)
R=[[] for _ in range(n+1)]
for _ in range(m):
    l,r,a=map(int,input().split())
    R[r].append((l,a))
for i in range(1,n+1):
    v=sst.query0(i)
    sst.add1(i,v)
    for l,a in R[i]:
        sst.add(l,i+1,a)
print(sst.query0(n+1))

Submission status: Time Limit Exceeded

Solution code:
class StarrySkyTree:
    def __init__(self,num):
        leaf=1<<(num-1).bit_length()
        self.leaf=leaf
        self.data=[0]*leaf*2
        self.lazy=[0]*leaf*2
        zero_indices=[]
        for i in range(num+1):
            tmp=[]
            i+=self.leaf
            limit=(i//(i&-i))>>1
            while i:
                if i<=limit:
                    tmp.append(i)
                i>>=1
            zero_indices.append(tmp)
        self.zero_indices=zero_indices
    def indices(self,l,r):
        L,R=l+self.leaf,r+self.leaf
        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 zeroindices(self,k):
        K=k+self.leaf
        limit=(K//(K&-K))>>1
        while K:
            if K<=limit:
                yield K
            K>>=1
    def _propagates(self,*ids):
        for i in reversed(ids):
            v=self.lazy[i-1]
            if v==0:
                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 add(self,l,r,x):
        L,R=l+self.leaf,r+self.leaf
        while L<R:
            if L&1:
                self.lazy[L-1]+=x; self.data[L-1]+=x
                L+=1
            if R&1:
                R-=1
                self.lazy[R-1]+=x; self.data[R-1]+=x
            L>>=1; R>>=1
        for i in self.indices(l,r):
            self.data[i-1]=max(self.data[2*i-1],self.data[2*i])+self.lazy[i-1]
    def add1(self,k,x):
        k+=self.leaf
        self.data[k-1]+=x
        while k:
            k>>=1
            self.data[k-1]=max(self.data[2*k-1],self.data[2*k])+self.lazy[k-1]
    def query0(self,k):
        self._propagates(*self.zeroindices(k))
        L,R=self.leaf,k+self.leaf
        ret=0
        while L<R:
            if L&1:
                ret=max(ret,self.data[L-1])
                L+=1
            if R&1:
                R-=1
                ret=max(ret,self.data[R-1])
            L>>=1; R>>=1
        return ret

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
sst=StarrySkyTree(n+1)
R=[[] for _ in range(n+1)]
for _ in range(m):
    l,r,a=map(int,input().split())
    R[r].append((l,a))
for i in range(1,n+1):
    v=sst.query0(i)
    sst.add1(i,v)
    for l,a in R[i]:
        sst.add(l,i+1,a)
print(sst.query0(n+1))

Submission status: Time Limit Exceeded

Solution code:
class StarrySkyTree:
    def __init__(self,num):
        leaf=1<<(num-1).bit_length()
        self.leaf=leaf
        self.data=[0]*leaf*2
        self.lazy=[0]*leaf*2
    def indices(self,l,r):
        L,R=l+self.leaf,r+self.leaf
        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):
        for i in reversed(ids):
            v=self.lazy[i-1]
            if v==0:
                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 add(self,l,r,x):
        L,R=l+self.leaf,r+self.leaf
        while L<R:
            if L&1:
                self.lazy[L-1]+=x; self.data[L-1]+=x
                L+=1
            if R&1:
                R-=1
                self.lazy[R-1]+=x; self.data[R-1]+=x
            L>>=1; R>>=1
        for i in self.indices(l,r):
            self.data[i-1]=max(self.data[2*i-1],self.data[2*i])+self.lazy[i-1]
    def add1(self,k,x):
        k+=self.leaf
        self.data[k-1]+=x
        while k:
            k>>=1
            self.data[k-1]=max(self.data[2*k-1],self.data[2*k])+self.lazy[k-1]
    def query(self,l,r):
        self._propagates(*self.indices(l,r))
        L,R=l+self.leaf,r+self.leaf
        ret=0
        while L<R:
            if L&1:
                ret=max(ret,self.data[L-1])
                L+=1
            if R&1:
                R-=1
                ret=max(ret,self.data[R-1])
            L>>=1; R>>=1
        return ret

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
sst=StarrySkyTree(n+1)
R=[[] for _ in range(n+1)]
for _ in range(m):
    l,r,a=map(int,input().split())
    R[r].append((l,a))
for i in range(1,n+1):
    v=sst.query(0,i)
    sst.add1(i,v)
    for l,a in R[i]:
        sst.add(l,i+1,a)
print(sst.query(0,n+1))

Submission status: Time Limit Exceeded

Solution code:
class StarrySkyTree:
    def __init__(self,num):
        leaf=1<<(num-1).bit_length()
        self.leaf=leaf
        self.data=[0]*leaf*2
        self.lazy=[0]*leaf*2
    def indices(self,l,r):
        L,R=l+self.leaf,r+self.leaf
        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):
        for i in reversed(ids):
            v=self.lazy[i-1]
            if v==0:
                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 add(self,l,r,x):
        L,R=l+self.leaf,r+self.leaf
        while L<R:
            if L&1:
                self.lazy[L-1]+=x; self.data[L-1]+=x
                L+=1
            if R&1:
                R-=1
                self.lazy[R-1]+=x; self.data[R-1]+=x
            L>>=1; R>>=1
        for i in self.indices(l,r):
            self.data[i-1]=max(self.data[2*i-1],self.data[2*i])+self.lazy[i-1]
    def query(self,l,r):
        self._propagates(*self.indices(l,r))
        L,R=l+self.leaf,r+self.leaf
        ret=0
        while L<R:
            if L&1:
                ret=max(ret,self.data[L-1])
                L+=1
            if R&1:
                R-=1
                ret=max(ret,self.data[R-1])
            L>>=1; R>>=1
        return ret

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
sst=StarrySkyTree(n+1)
R=[[] for _ in range(n+1)]
for _ in range(m):
    l,r,a=map(int,input().split())
    R[r].append((l,a))
for i in range(1,n+1):
    v=sst.query(0,i)
    sst.add(i,i+1,v)
    for l,a in R[i]:
        sst.add(l,i+1,a)
print(sst.query(0,n+1))

Submission status: Time Limit Exceeded

Solution code:
class StarrySkyTree:
    def __init__(self,param,default,func):
        if isinstance(param,list):
            num=len(param)
        else:
            num=param
        leaf=1<<(num-1).bit_length()
        self.leaf=leaf
        self.d=default
        if isinstance(param,list):
            self.data=[default]*(leaf-1)+param+[default]*(leaf-num+1)
            for i in range(self.leaf-2,-1,-1):
                self.data[i]=func(self.data[i*2],self.data[i*2+1])
        else:
            self.data=[default]*leaf*2
        self.lazy=[0]*leaf*2
        self.f=func
    def merge(self,a,b):
        return self.f(a,b)
    def indices(self,l,r):
        L,R=l+self.leaf,r+self.leaf
        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):
        for i in reversed(ids):
            v=self.lazy[i-1]
            if v==0:
                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 add(self,l,r,x):
        *ids,=self.indices(l,r)
        self._propagates(*ids)
        L,R=l+self.leaf,r+self.leaf
        while L<R:
            if L&1:
                self.lazy[L-1]+=x; self.data[L-1]+=x
                L+=1
            if R&1:
                R-=1
                self.lazy[R-1]+=x; self.data[R-1]+=x
            L>>=1; R>>=1
        for i in ids:
            self.data[i-1]=self.merge(self.data[2*i-1],self.data[2*i])
    def query(self,l,r):
        self._propagates(*self.indices(l,r))
        L,R=l+self.leaf,r+self.leaf
        ret=self.d
        while L<R:
            if L&1:
                ret=self.merge(ret,self.data[L-1])
                L+=1
            if R&1:
                R-=1
                ret=self.merge(ret,self.data[R-1])
            L>>=1; R>>=1
        return ret

import sys
input=sys.stdin.readline
n,m=map(int,input().split())

def f(a,b):
    return max(a,b)

sst=StarrySkyTree(n+1,0,f)
R=[[] for _ in range(n+1)]
for _ in range(m):
    l,r,a=map(int,input().split())
    R[r].append((l,a))
for i in range(1,n+1):
    v=sst.query(0,i)
    sst.add(i,i+1,v)
    for l,a in R[i]:
        sst.add(l,i+1,a)
print(sst.query(0,n+1))

Submission status: Time Limit Exceeded

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

N,M=map(int,input().split())

end=[[] for i in range(N+2)]

for i in [0]*M:
    l,r,a=map(int,input().split())
    end[r+1].append((l,a))

#Starry Sky tree
seg_el=1<<18#Segment treeの台の要素数

SEG=[0]*(2*seg_el-1)#Segment tree.色々考えると0で初期化してOKそう
ADD=[0]*(2*seg_el-1)#加算用Segment tree,SEG[k]+ADD[k]がkにおける本当の最大値

def updates(a,b,x,k,l,r):#区間[a,b)にxを加算
    
    if a==l and r==b:
        ADD[k]+=x#そのノードのADD値を更新
        return

    if a>=(r+l)//2:
        updates(a,b,x,k*2+2,(l+r)//2,r)#左側の子のみを見る
    elif b<=(r+l)//2:
        updates(a,b,x,k*2+1,l,(l+r)//2)#右側の子のみを見る
    else:
        updates(a,(l+r)//2,x,k*2+1,l,(l+r)//2)#それ以外のときは,SEG[k*2+1]とSEG[k*2+2]で場合分け
        updates((l+r)//2,b,x,k*2+2,(l+r)//2,r)

    SEG[k]=max(SEG[k*2+1]+ADD[k*2+1],SEG[k*2+2]+ADD[k*2+2])

def update_solo(n,x,seg_el):#A[n]=xに更新（反映）
    i=n+seg_el-1
    SEG[i]=x
    i=(i-1)//2
    
    while i>=0:
        SEG[i]=max(SEG[i*2+1]+ADD[i*2+1],SEG[i*2+2]+ADD[i*2+2])
        i=(i-1)//2

for i in range(1,N+2):

    for b,x in end[i]:
        updates(b,i,x,0,0,seg_el)#点数がもらえる区間から出たときにその分を加算

    update_solo(i,SEG[0],seg_el)#[0,i)の最大値はSEG[0](=SEG[0]+ADD[0])と一致するはず

print(SEG[0])

Submission status: Time Limit Exceeded

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

N,M=map(int,input().split())

end=[[] for i in range(N+2)]

for i in [0]*M:
    l,r,a=map(int,input().split())
    end[r+1].append((l,a))

#Starry Sky tree
seg_el=1<<18#Segment treeの台の要素数

SEG=[0]*(2*seg_el-1)#Segment tree.色々考えると0で初期化してOKそう
ADD=[0]*(2*seg_el-1)#加算用Segment tree,SEG[k]+ADD[k]がkにおける本当の最大値
seg_el_list=[524286, 262142, 131070, 65534, 32766, 16382, 8190, 4094, 2046, 1022, 510, 254, 126, 62, 30, 14, 6, 2, 0]
#seg_el_list=[14, 6, 2, 0]

def update(k):#SEGのkより上のノードを更新（反映）
    while k>=0:
        k=(k-1)//2
        SEG[k]=max(SEG[k*2+1]+ADD[k*2+1],SEG[k*2+2]+ADD[k*2+2])

def to_seg(a):#aが終点となる区間をSegment treeの座標へ変換  
    b=(a&(-a)).bit_length()
    return seg_el_list[b]+a//(1<<(b-1))

def add(a,b,x):#区間(a,b]にxを加算
    #print(a,b,x)
    while b!=0:
        ADD[to_seg(b)]+=x
        update(to_seg(b))
        b-=(b&(-b))

    while a!=0:
        ADD[to_seg(a)]+=-x
        update(to_seg(a))
        a-=(a&(-a))
    
for i in range(N+2):
    for b,k in end[i]:
        add(b,i,k)#点数がもらえる区間から出たときにその分を加算

    SEG[i+seg_el-1]=SEG[0]
    update(i+seg_el-1)

print(SEG[0])

Submission status: Time Limit Exceeded

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

N,M=map(int,input().split())

end=[[] for i in range(N+2)]

for i in [0]*M:
    l,r,a=map(int,input().split())
    end[r+1].append((l,a))

#Starry Sky tree
seg_el=1<<18#Segment treeの台の要素数

seg_el_list=[]
i=seg_el-1
while i>=0:
    seg_el_list.append(i)
    i=(i-1)//2

SEG=[0]*(2*seg_el-1)#Segment tree.色々考えると0で初期化してOKそう
ADD=[0]*(2*seg_el-1)#加算用Segment tree,SEG[k]+ADD[k]がkにおける本当の最大値

def updates(a,b,x,k,l,r):#区間[a,b)にxを加算
    
    if r<=a or b<=l:#区間[a,b)が対象区間の外にあれば終了
        return
    
    if a<=l and r<=b:
        ADD[k]+=x#そのノードのADD値を更新
        return
    
    updates(a,b,x,k*2+1,l,(l+r)>>1)#それ以外のときは,SEG[k*2+1]とSEG[k*2+2]で場合分け
    updates(a,b,x,k*2+2,(l+r)>>1,r)

    SEG[k]=max(SEG[k*2+1]+ADD[k*2+1],SEG[k*2+2]+ADD[k*2+2])

def update_solo(n,x):#A[n]=xに更新（反映）
    i=n+seg_el-1
    SEG[i]=x
    i=(i-1)//2
    
    while i>=min_seg_el:
        SEG[i]=max(SEG[i*2+1]+ADD[i*2+1],SEG[i*2+2]+ADD[i*2+2])
        i=(i-1)//2

for i in range(1,N+2):
    i_bit=i.bit_length()
    min_seg_el=seg_el_list[i_bit]

    for b,x in end[i]:
        updates(b,i,x,min_seg_el,0,1<<i_bit)#点数がもらえる区間から出たときにその分を加算

    update_solo(i,SEG[min_seg_el]+ADD[min_seg_el])#[0,i)の最大値はSEG[0]+ADD[0]と一致するはず

print(SEG[min_seg_el]+ADD[min_seg_el])

Submission status: Time Limit Exceeded

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

N,M=map(int,input().split())

end=[[] for i in range(N+2)]
LIST=set()#更新が必要な座標を選ぶ

for i in [0]*M:
    l,r,a=map(int,input().split())
    end[r+1].append((l,a))
    LIST.add(r)
    LIST.add(r+1)

#Starry Sky tree
seg_el=1<<18#Segment treeの台の要素数

SEG=[0]*(2*seg_el-1)#Segment tree.色々考えると0で初期化してOKそう
ADD=[0]*(2*seg_el-1)#加算用Segment tree,SEG[k]+ADD[k]がkにおける本当の最大値

def updates(a,b,x,k,l,r):#区間[a,b)にxを加算
    
    if r<=a or b<=l:#区間[a,b)が対象区間の外にあれば終了
        return
    
    if a<=l and r<=b:
        ADD[k]+=x#そのノードのADD値を更新
        return
    
    updates(a,b,x,k*2+1,l,(l+r)//2)#それ以外のときは,SEG[k*2+1]とSEG[k*2+2]で場合分け
    updates(a,b,x,k*2+2,(l+r)//2,r)

    SEG[k]=max(SEG[k*2+1]+ADD[k*2+1],SEG[k*2+2]+ADD[k*2+2])

def update_solo(n,x,seg_el):#A[n]=xに更新（反映）
    i=n+seg_el-1
    SEG[i]=x
    i=(i-1)//2
    
    while i>=0:
        SEG[i]=max(SEG[i*2+1]+ADD[i*2+1],SEG[i*2+2]+ADD[i*2+2])
        i=(i-1)//2

for i in sorted(LIST) :

    for b,x in end[i]:
        updates(b,i,x,0,0,seg_el)#点数がもらえる区間から出たときにその分を加算

    update_solo(i,SEG[0]+ADD[0],seg_el)#[0,i)の最大値はSEG[0]+ADD[0]と一致するはず

print(SEG[0]+ADD[0])

Submission status: Time Limit Exceeded

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

N,M=map(int,input().split())

end=[[] for i in range(N+2)]
LIST=set()#更新が必要な座標を選ぶ

for i in [0]*M:
    l,r,a=map(int,input().split())
    end[r+1].append((l,a))
    LIST.add(l)
    LIST.add(r)
    LIST.add(r+1)

LIST=sorted(LIST)

#Starry Sky tree
seg_el=1<<18#Segment treeの台の要素数

SEG=[0]*(2*seg_el-1)#Segment tree.色々考えると0で初期化してOKそう
ADD=[0]*(2*seg_el-1)#加算用Segment tree,SEG[k]+ADD[k]がkにおける本当の最大値

def updates(a,b,x,k,l,r):#区間[a,b)にxを加算
    
    if r<=a or b<=l:#区間[a,b)が対象区間の外にあれば終了
        return
    
    if a<=l and r<=b:
        ADD[k]+=x#そのノードのADD値を更新
        return
    
    updates(a,b,x,k*2+1,l,(l+r)//2)#それ以外のときは,SEG[k*2+1]とSEG[k*2+2]で場合分け
    updates(a,b,x,k*2+2,(l+r)//2,r)

    SEG[k]=max(SEG[k*2+1]+ADD[k*2+1],SEG[k*2+2]+ADD[k*2+2])

def update_solo(n,x,seg_el):#A[n]=xに更新（反映）
    i=n+seg_el-1
    SEG[i]=x
    i=(i-1)//2
    
    while i>=0:
        SEG[i]=max(SEG[i*2+1]+ADD[i*2+1],SEG[i*2+2]+ADD[i*2+2])
        i=(i-1)//2

for i in LIST:

    for b,x in end[i]:
        updates(b,i,x,0,0,seg_el)#点数がもらえる区間から出たときにその分を加算

    update_solo(i,SEG[0]+ADD[0],seg_el)#[0,i)の最大値はSEG[0]+ADD[0]と一致するはず

print(SEG[0]+ADD[0])

Submission status: Time Limit Exceeded

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

N,M=map(int,input().split())

end=[[] for i in range(N+2)]

for i in [0]*M:
    l,r,a=map(int,input().split())
    end[r+1].append((l,a))

#Starry Sky tree
seg_el=1<<18#Segment treeの台の要素数

SEG=[0]*(2*seg_el-1)#Segment tree.色々考えると0で初期化してOKそう
ADD=[0]*(2*seg_el-1)#加算用Segment tree,SEG[k]+ADD[k]がkにおける本当の最大値

def updates(a,b,x,k,l,r):#区間[a,b)にxを加算
    
    if r<=a or b<=l:#区間[a,b)が対象区間の外にあれば終了
        return
    
    if a<=l and r<=b:
        ADD[k]+=x#そのノードのADD値を更新
        return
    
    updates(a,b,x,k*2+1,l,(l+r)>>1)#それ以外のときは,SEG[k*2+1]とSEG[k*2+2]で場合分け
    updates(a,b,x,k*2+2,(l+r)>>1,r)

    SEG[k]=max(SEG[k*2+1]+ADD[k*2+1],SEG[k*2+2]+ADD[k*2+2])

def update_solo(n,x,seg_el):#A[n]=xに更新（反映）
    i=n+seg_el-1
    SEG[i]=x
    i=(i-1)//2
    
    while i>=0:
        SEG[i]=max(SEG[i*2+1]+ADD[i*2+1],SEG[i*2+2]+ADD[i*2+2])
        i=(i-1)//2

for i in range(1,N+2):

    for b,x in end[i]:
        updates(b,i,x,0,0,seg_el)#点数がもらえる区間から出たときにその分を加算

    update_solo(i,SEG[0]+ADD[0],seg_el)#[0,i)の最大値はSEG[0]+ADD[0]と一致するはず

print(SEG[0]+ADD[0])