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: Runtime Error

Solution code:
"""
遅延セグメント木（区間演算、区間更新）
dat[] の要素に モノイド M をもつ
laz[] の要素に Aut(M) をもつ（ただし作用素は「右」から作用とする）
アクセスは0-indexed, 内部のツリーは 1-indexed（つまりすべての和は tree[1]）
関数は閉区間
引数：
    N: 処理する区間の長さ
    op_M = operator: モノイド演算 (max, min, __add__,ラムダ式,関数定義など)
    e_M: 単位元
    compose: 作用素を合成させる関数 (max, min, __add__,ラムダ式,関数定義など)
    funcval(x,f) = f(x) 関数適用
    ID_M: 恒等作用素
"""
""" 作用素の例：
f \mapsto min(f,-)
    compose = min
    funcval = min
    ID_M = INF = 10**18
f \mapsto max(f,-)
    compose = max
    funcval = max
    ID_M = 0
f \mapsto f (定数関数)（区間代入、最後の操作のみが影響する）
compose = lambda f,g: (f if g == ID_M else g)
funcval = lambda x,f: (x if f == ID_M else f)
ID_M = None #Noneではなく、範囲外の数にすると速くなる
"""

class lazy_segment_tree:
    def __init__(self, N, operator_M, e_M, compose, funcval, ID_M=None):
        self.compose = compose #作用素の合成（右から）
        self.ID_M = ID_M       #恒等作用素
        self.funcval = funcval #関数適用

        self.op_M = operator_M # Mの演算
        self.e_M = e_M         # Mの単位元
        ####################################
        self.height = (N-1).bit_length() #木の段数
        self.N0 = N0 = 1<<self.height #木の横幅 >= N

        self.dat = [self.e_M]*(2*N0) #データの木
        self.laz = [self.ID_M]*(2*N0) #作用素の木
        
        """
        length = [N0>>1]*N0
        for i in range(2,N0): length[i] = length[i>>1]>>1
        self.length = length #区間の長さ
        """
        
    # 長さNの配列 initial で dat を初期化
    def build(self, initial):
        self.dat[self.N0:self.N0+len(initial)] = initial[:]
        for k in range(self.N0-1,0,-1):
            self.dat[k] = self.op_M(self.dat[2*k], self.dat[2*k+1])
    
    # dat[k] に laz[k] を適用して、laz[k] を伝播
    def propagate(self,k):
        if self.laz[k] == self.ID_M: return;
        self.dat[k] = self.funcval(self.dat[k],self.laz[k])

        if self.N0 <= k:
            self.laz[k] = self.ID_M
            return
        else:
            self.laz[2*k  ] = self.compose(self.laz[2*k  ],self.laz[k])
            self.laz[2*k+1] = self.compose(self.laz[2*k+1],self.laz[k])
            self.laz[k] = self.ID_M
            return
        
    # 遅延をすべて解消する
    def propagate_all(self):
        for i in range(1,2*self.N0): self.propagate(i)
    
    # laz[k]およびその上に位置する作用素をすべて伝播
    def thrust(self,k):
        for i in range(self.height,-1,-1): self.propagate(k>>i)

    def thrust2(self,L,R):
        for i in range(self.height,0,-1):
            self.propagate(L>>i)
            if (L>>i) != R>>i:
                self.propagate(R>>i)

    # 区間[l,r]に関数 f を作用
    def update(self, l,r,f):
        l += self.N0; r += self.N0
        #まず伝播させる #self.thrust(l>>1); self.thrust(r>>1)
        self.thrust2(l,r)
        L = l; R = r+1
        #[l.r]に対応する区間たちに関数 f を適用
        while L < R:
            if R & 1:
                R -= 1
                self.laz[R] = self.compose(self.laz[R], f)
            if L & 1:
                self.laz[L] = self.compose(self.laz[L], f)
                L += 1
            L >>= 1; R >>= 1
        # 再計算 #self.recalc_dat(l); self.recalc_dat(r)
        self.recalc_dat2(l,r)
        
    #def reflect(self,k):
    #    if self.laz[k] == self.ID_M: return self.dat[k]
    #    else: return self.funcval(self.dat[k],self.laz[k])
        
    # dat[k] を更新したときに上部を再計算
    def recalc_dat(self,k):
        k >>= 1
        while k:
            self.dat[k] = self.op_M(self.funcval(self.dat[2*k],self.laz[2*k]),self.funcval(self.dat[2*k+1],self.laz[2*k+1]))
            #self.dat[k] = self.op_M(self.reflect(2*k),self.reflect(2*k+1)))
            k >>= 1

    def recalc_dat2(self,l,r):
        l >>= 1; r >>= 1
        while l:
            #self.dat[l] = self.op_M(self.reflect(2*l),self.reflect(2*l+1))
            self.dat[l] = self.op_M(self.funcval(self.dat[2*l],self.laz[2*l]),self.funcval(self.dat[2*l+1],self.laz[2*l+1]))
            if l != r:
                #self.dat[r] = self.op_M(self.reflect(2*r),self.reflect(2*r+1))
                self.dat[r] = self.op_M(self.funcval(self.dat[2*r],self.laz[2*r]),self.funcval(self.dat[2*r+1],self.laz[2*r+1]))
            l >>= 1; r >>= 1

    # val[k] を取得。
    def point_get(self, k):
        k += self.N0
        res = self.dat[k]
        while k:
            if self.laz[k] != self.ID_M:
                res = self.funcval(res, self.laz[k])
            k >>= 1
        return res
    
    # values[k] = x 代入する
    def point_set(self, k,x): 
        k += self.N0
        self.thrust(k)
        self.dat[k] = x
        self.recalc_dat(k)

    # 区間[L,R]をopでまとめる
    def query(self, L,R):
        L += self.N0; R += self.N0 + 1 
        self.thrust2(L,R)
        #self.thrust(L); self.thrust(R-1)
        sl = sr = self.e_M
        while L < R:
            if R & 1:
                R -= 1
                sr = self.op_M(self.funcval(self.dat[R],self.laz[R]),sr)
            if L & 1:
                sl = self.op_M(sl,self.funcval(self.dat[L],self.laz[L]))
                L += 1
            L >>= 1; R >>= 1
        return self.op_M(sl,sr)


###########################################################################
###########################################################################
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.buffer.readline 

n,m = [int(i) for i in readline().split()]
lra = [tuple(int(i) for i in readline().split()) for _ in range(m)]

from operator import add, itemgetter
operator_M = max
compose = add
funcval = add
ID_M = 0
e_M = -10**18

seg = lazy_segment_tree(n+1, operator_M, e_M, compose, funcval, ID_M)
seg.build([0]+[ID_M]*(n))

#seg.build([0]*n)

ans = [] 

lra.sort(key = itemgetter(1))

j = 0

"""
N0 = self.N0
self.thrust(k)
self.dat[k] = x
self.recalc_dat(k)
"""

N0 = seg.N0
for i in range(1,n+1):
    #print(seg.laz,seg.dat,i,seg.query(0,i-1))
    #seg.point_set(i,seg.query(0,i-1))
    
    seg.dat[i+N0] = seg.query(0,i-1)
    seg.recalc_dat(i+N0)
    
    while j < m and i == lra[j][1]:
        #print("hoge")
        seg.update(*lra[j])#[0],lra[j][1],lra[j][2])
        j += 1

seg.propagate_all()
print(max(seg.dat[seg.N0:seg.N0+n+1]))


#print(seg.laz,seg.dat)

assert n != 1

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    a = list(map(int, input().split()))
    c1, c2, c3 = 0, 0, 0
    for ai in a:
        if ai == 1:
            c1+=1
        elif ai == 2:
            c2 += 1
        else:
            c3 += 1
    dp = [[[0]*(N+1) for i in range(N+1)] for j in range(c3+1)]

    for i in range(c3+1):
        for j in range(N+1):
            for k in range(N+1):
                try:
                    dp[i][j][k] = ((i/N)*dp[i-1][j+1][k]+(j/N)*dp[i][j-1][k+1]+(k/N)*dp[i][j][k-1]+1)*N / (i+j+k)
                except IndexError:
                    continue
                except ZeroDivisionError:
                    continue
    print(dp[c3][c2][c1])
main()

Submission status: Runtime Error

Solution code:
#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]

def update(k):#SEGのkより上のノードを更新（反映）
    while k>=0:
        k=(k-1)//2
        if SEG[k]==max(SEG[k*2+1]+ADD[k*2+1],SEG[k*2+2]+ADD[k*2+2]):
            break
        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: Runtime Error

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

N,M=map(int,input().split())
SCORE=[list(map(int,input().split())) for i in range(M)]

SUM=[0]*(N+2)
start=[[] for i in range(N+2)]
end=[[] for i in range(N+2)]

for i in range(M):
    start[SCORE[i][0]].append(i)
    end[SCORE[i][1]+1].append(i)
    SUM[SCORE[i][0]]+=SCORE[i][2]
    SUM[SCORE[i][1]+1]-=SCORE[i][2]

import itertools
SUM=list(itertools.accumulate(SUM))


#遅延Segment tree

for i in range(30):#要素数以上の2のベキを見つける
    if N<1<<i:
        seg_el=1<<i#Segment treeの台の要素数
        break

seg_el2=seg_el-1#Segment treeの一段目の最初の要素

SEG=[0]*(2*seg_el-1)#Segment tree
LAZY=[0]*(2*seg_el-1)#子ノードへの伝搬用Segment tree

def propagation(k):#子ノードへ伝搬
    
    if LAZY[k]!=0 and k<seg_el2:
        lazy_item=LAZY[k]
        LAZY[k]=0

        LAZY[k*2+1]+=lazy_item
        LAZY[k*2+2]+=lazy_item
        SEG[k*2+1]+=lazy_item
        SEG[k*2+2]+=lazy_item

def updates(a,b,x,k,l,r):#区間[a,b)にxを加算
    propagation(k)#アクセスした箇所にデータが入っていたときは,評価を伝搬させる
    
    if r<=a or b<=l:#区間[a,b)が対象区間の外にあれば終了
        return
    
    if a<=l and r<=b:
        SEG[k]+=x#そのノードを更新
        LAZY[k]+=x#後でアクセスされたときに子ノードを更新
        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)

    if SEG[k*2+1]>SEG[k*2+2]:#そのノードを更新（再帰的に値が求まる）
        SEG[k]=SEG[k*2+1]
    else:
        SEG[k]=SEG[k*2+2]


def getvalues(a,b,k,l,r):#区間[a,b)での,SEG[k],つまり区間[l,r)に関する最大値を調べる
    
    if r<=a or b<=l:#区間[a,b)が対象区間の外にあれば,-infを出力
        return -float("inf")
    
    if a<=l and r<=b:#区間[a,b)が対象区間の中にあればSEG[k]を出力
        return SEG[k]
    
    propagation(k)#アクセスした箇所にデータが入っていたときは,評価を伝搬させる
    
    vl=getvalues(a,b,k*2+1,l,(l+r)//2)#それ以外のときは,SEG[k*2+1]とSEG[k*2+2]で場合分け（木の子ノード二つを見る）
    vr=getvalues(a,b,k*2+2,(l+r)//2,r)

    if vl>vr:
        return vl
    else:
        return vr

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:
        if SEG[i*2+1]>SEG[i*2+2]:
            SEG[i]=SEG[i*2+1]
        else:
            SEG[i]=SEG[i*2+2]
        i=(i-1)//2

for i in range(1,N+2):
    
    for j in start[i]:
        l,r,s=SCORE[j]
        updates(l,r+1,-s,0,0,seg_el)
    for j in end[i]:
        l,r,s=SCORE[j]
        updates(l,r+1,s,0,0,seg_el)

    #print(SEG)

    update_solo(i,getvalues(0,i,0,0,seg_el)+SUM[i],seg_el)

    #print(SEG)


print(getvalues(0,N+1,0,0,seg_el))

Submission status: Runtime Error

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)

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)

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, k, x):
    propagates(I[k])

    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 I[k]:
        data[i-1] = max(data[2*i-1], data[2*i])

def update(r, x):
    __update(0, r, r, x)

def update1(k, x):
    __update(k, k+1, k, x)

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


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