#811029 (PyPy3) No.844 split game

提出ソース
結果

問題	No.844 split game
ユーザー	vwxyz
提出日時	2022-10-26 12:30:32
言語	PyPy3 (7.3.15)
結果	AC
実行時間	455 ms / 2,000 ms
コード長	22,369 bytes
コンパイル時間	1,284 ms
コンパイル使用メモリ	82,304 KB
実行使用メモリ	115,072 KB
最終ジャッジ日時	2024-07-04 02:59:58
合計ジャッジ時間	18,269 ms
ジャッジサーバーID （参考情報）	judge3 / judge5
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	262 ms 98,520 KB
testcase_01	AC	291 ms 105,584 KB
testcase_02	AC	323 ms 103,884 KB
testcase_03	AC	321 ms 107,776 KB
testcase_04	AC	262 ms 97,408 KB
testcase_05	AC	418 ms 111,104 KB
testcase_06	AC	289 ms 97,180 KB
testcase_07	AC	286 ms 100,764 KB
testcase_08	AC	270 ms 94,312 KB
testcase_09	AC	305 ms 99,072 KB
testcase_10	AC	413 ms 107,776 KB
testcase_11	AC	431 ms 113,120 KB
testcase_12	AC	283 ms 99,140 KB
testcase_13	AC	280 ms 96,128 KB
testcase_14	AC	361 ms 101,608 KB
testcase_15	AC	414 ms 114,304 KB
testcase_16	AC	454 ms 113,920 KB
testcase_17	AC	433 ms 114,036 KB
testcase_18	AC	416 ms 115,072 KB
testcase_19	AC	455 ms 114,076 KB
testcase_20	AC	420 ms 114,816 KB
testcase_21	AC	417 ms 114,048 KB
testcase_22	AC	431 ms 113,984 KB
testcase_23	AC	223 ms 91,476 KB
testcase_24	AC	254 ms 93,172 KB
testcase_25	AC	193 ms 90,564 KB
testcase_26	AC	211 ms 91,264 KB
testcase_27	AC	207 ms 91,220 KB
testcase_28	AC	206 ms 91,008 KB
testcase_29	AC	269 ms 92,976 KB
testcase_30	AC	238 ms 92,672 KB
testcase_31	AC	222 ms 91,688 KB
testcase_32	AC	216 ms 91,112 KB
testcase_33	AC	177 ms 90,880 KB
testcase_34	AC	169 ms 90,496 KB
testcase_35	AC	178 ms 90,752 KB
testcase_36	AC	175 ms 91,004 KB
testcase_37	AC	191 ms 91,648 KB
testcase_38	AC	244 ms 94,744 KB
testcase_39	AC	310 ms 100,864 KB
testcase_40	AC	250 ms 99,812 KB
testcase_41	AC	144 ms 88,732 KB
testcase_42	AC	142 ms 88,448 KB
testcase_43	AC	143 ms 88,704 KB
testcase_44	AC	144 ms 88,744 KB
testcase_45	AC	141 ms 88,832 KB
testcase_46	AC	139 ms 88,576 KB
testcase_47	AC	142 ms 88,704 KB
testcase_48	AC	140 ms 88,448 KB
testcase_49	AC	141 ms 88,636 KB
testcase_50	AC	141 ms 88,704 KB
testcase_51	AC	141 ms 88,448 KB
testcase_52	AC	144 ms 88,704 KB
testcase_53	AC	141 ms 88,704 KB
testcase_54	AC	142 ms 88,576 KB
testcase_55	AC	145 ms 88,704 KB
testcase_56	AC	141 ms 88,576 KB
testcase_57	AC	142 ms 88,704 KB
testcase_58	AC	146 ms 88,704 KB
testcase_59	AC	145 ms 88,448 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
import bisect
import copy
import decimal
import fractions
import heapq
import itertools
import math
import random
import sys
import time
from collections import Counter,deque,defaultdict
from functools import lru_cache,reduce
from heapq import heappush,heappop,heapify,heappushpop,_heappop_max,_heapify_max
def _heappush_max(heap,item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappushpop_max(heap, item):
    if heap and item < heap[0]:
        item, heap[0] = heap[0], item
        heapq._siftup_max(heap, 0)
    return item
from math import gcd as GCD
read=sys.stdin.read
readline=sys.stdin.readline
readlines=sys.stdin.readlines
write=sys.stdout.write

class Segment_Tree:
    def __init__(self,N,f,e,lst=None,dynamic=False):
        self.f=f
        self.e=e
        self.N=N
        if dynamic:
            self.segment_tree=defaultdict(lambda:self.e)
        else:
            if lst==None:
                self.segment_tree=[self.e]*2*self.N
            else:
                assert len(lst)<=self.N
                self.segment_tree=[self.e]*self.N+[x for x in lst]+[self.e]*(N-len(lst))
                for i in range(self.N-1,0,-1):
                    self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])

    def __getitem__(self,i):
        if type(i)==int:
            if -self.N<=i<0:
                return self.segment_tree[i+self.N*2]
            elif 0<=i<self.N:
                return self.segment_tree[i+self.N]
            else:
                raise IndexError("list index out of range")
        else:
            a,b,c=i.start,i.stop,i.step
            if a==None:
                a=self.N
            else:
                a+=self.N
            if b==None:
                b=self.N*2
            else:
                b+=self.N
            return self.segment_tree[slice(a,b,c)]

    def __setitem__(self,i,x):
        if -self.N<=i<0:
            i+=self.N*2
        elif 0<=i<self.N:
            i+=self.N
        else:
            raise IndexError("list index out of range")
        self.segment_tree[i]=x
        while i>1:
            i>>= 1
            self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])

    def Build(self,lst):
        for i,x in enumerate(lst,self.N):
            self.segment_tree[i]=x
        for i in range(self.N-1,0,-1):
            self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])

    def Fold(self,L=None,R=None):
        if L==None:
            L=self.N
        else:
            L+=self.N
        if R==None:
            R=self.N*2
        else:
            R+=self.N
        vL=self.e
        vR=self.e
        while L<R:
            if L&1:
                vL=self.f(vL,self.segment_tree[L])
                L+=1
            if R&1:
                R-=1
                vR=self.f(self.segment_tree[R],vR)
            L>>=1
            R>>=1
        return self.f(vL,vR)

    def Fold_Index(self,L=None,R=None):
        if L==None:
            L=self.N
        else:
            L+=self.N
        if R==None:
            R=self.N*2
        else:
            R+=self.N
        if L==R:
            return None
        x=self.Fold(L-self.N,R-self.N)
        while L<R:
            if L&1:
                if self.segment_tree[L]==x:
                    i=L
                    break
                L+=1
            if R&1:
                R-=1
                if self.segment_tree[R]==x:
                    i=R
                    break
            L>>=1
            R>>=1
        while i<self.N:
            if self.segment_tree[i]==self.segment_tree[i<<1]:
                i<<=1
            else:
                i<<=1
                i|=1
        i-=self.N
        return i

    def Bisect_Right(self,L=None,f=None):
        if L==self.N:
            return self.N
        if L==None:
            L=0
        L+=self.N
        vl=self.e
        vr=self.e
        l,r=L,self.N*2
        while l<r:
            if l&1:
                vl=self.f(vl,self.segment_tree[l])
                l+=1
            if r&1:
                r-=1
                vr=self.f(self.segment_tree[r],vr)
            l>>=1
            r>>=1
        if f(self.f(vl,vr)):
            return self.N
        v=self.e
        while True:
            while L%2==0:
                L>>=1
            vv=self.f(v,self.segment_tree[L])
            if f(vv):
                v=vv
                L+=1
            else:
                while L<self.N:
                    L<<=1
                    vv=self.f(v,self.segment_tree[L])
                    if f(vv):
                        v=vv
                        L+=1
                return L-self.N

    def Bisect_Left(self,R=None,f=None):
        if R==0:
            return 0
        if R==None:
            R=self.N
        R+=self.N
        vl=self.e
        vr=self.e
        l,r=self.N,R
        while l<r:
            if l&1:
                vl=self.f(vl,self.segment_tree[l])
                l+=1
            if r&1:
                r-=1
                vr=self.f(self.segment_tree[r],vr)
            l>>=1
            r>>=1
        if f(self.f(vl,vr)):
            return 0
        v=self.e
        while True:
            R-=1
            while R>1 and R%2:
                R>>=1
            vv=self.f(self.segment_tree[R],v)
            if f(vv):
                v=vv
            else:
                while R<self.N:
                    R=2*R+1
                    vv=self.f(self.segment_tree[R],v)
                    if f(vv):
                        v=vv
                        R-=1
                return R+1-self.N

    def __str__(self):
        return "["+", ".join(map(str,self.segment_tree[self.N:]))+"]"

class Segment_Tree2:
    def __init__(self,N,M,f,e,lst=None,dynamic=False):
        self.N=N
        self.M=M
        self.f=f
        self.e=e
        if dynamic:
            self.segment_tree=defaultdict(lambda:defaultdict(lambda:e))
        else:
            if lst==None:
                self.segment_tree=[[self.e]*2*self.M for i in range(2*self.N)]
            else:
                assert len(lst)<=self.N
                assert all(len(lst[i])<=self.M for i in range(self.N))
                self.segment_tree=[[self.e]*2*self.M for i in range(self.N)]+[[self.e]*self.M+lst[i]+[self.e]*(self.M-len(lst[i])) for i in range(len(lst))]+[[self.e]*2*self.M for i in range(self.N-len(lst))]
                for i in range(self.N-1,0,-1):
                    for j in range(2*self.M-1,self.M-1,-1):
                        self.segment_tree[i][j]=self.f(self.segment_tree[i<<1][j],self.segment_tree[i<<1|1][j])
                for i in range(2*self.N-1,-1,-1):
                    for j in range(self.M-1,0,-1):
                        self.segment_tree[i][j]=self.f(self.segment_tree[i][j<<1],self.segment_tree[i][j<<1|1])

    def __getitem__(self,tpl):
        i,j=tpl
        i+=self.N
        j+=self.M
        return self.segment_tree[i][j]

    def __setitem__(self,tpl,x):
        i,j=tpl
        i+=self.N
        j+=self.M
        self.segment_tree[i][j]=x
        idxN=[i]
        idxM=[j]
        while i>1:
            i>>=1
            idxN.append(i)
        while j>1:
            j>>=1
            idxM.append(j)
        i=idxN[0]
        for j in idxM[1:]:
            self.segment_tree[i][j]=self.f(self.segment_tree[i][j<<1],self.segment_tree[i][j<<1|1])
        for i in idxN[1:]:
            for j in idxM:
                self.segment_tree[i][j]=self.f(self.segment_tree[i<<1][j],self.segment_tree[i<<1|1][j])

    def Build(self,lst):
        assert len(lst)<=self.N
        assert all(len(lst[i] for i in range(self.N))<=self.M)
        for i in range(len(lst)):
            for j in range(len(lst[i])):
                self.segment_tree[i+self.N][j+self.M]=lst[i][j]
        for i in range(self.N-1,0,-1):
            for j in range(2*self.M-1,self.M-1,-1):
                self.segment_tree[i][j]=self.f(self.segment_tree[i<<1][j],self.segment_tree[i<<1|1][j])
        for i in range(2*self.N-1,-1,-1):
            for j in range(self.M-1,0,-1):
                self.segment_tree[i][j]=self.f(self.segment_tree[i][j<<1],self.segment_tree[i][j<<1|1])

    def Fold(self,LN=None,RN=None,LM=None,RM=None):
        LN+=self.N
        RN+=self.N
        LM+=self.M
        RM+=self.M
        idxN=[]
        idxM=[]
        while LN<RN:
            if LN&1:
                idxN.append(LN)
                LN+=1
            if RN&1:
                RN-=1
                idxN.append(RN)
            LN>>=1
            RN>>=1
        while LM<RM:
            if LM&1:
                idxM.append(LM)
                LM+=1
            if RM&1:
                RM-=1
                idxM.append(RM)
            LM>>=1
            RM>>=1
        retu=self.e
        for i in idxN:
            for j in idxM:
                retu=self.f(retu,self.segment_tree[i][j])
        return retu

    def Fold_Index(self,LN=None,RN=None,LM=None,RM=None):
        if LN==None:
            LN=self.N
        else:
            LN+=self.N
        if RN==None:
            RN=self.N*2
        else:
            RN+=self.N
        if LM==None:
            LM=self.M
        else:
            LM+=self.M
        if RM==None:
            RM=self.M*2
        else:
            RM+=self.M
        if LN==RN and LM==RM:
            return None
        idxN=[]
        idxM=[]
        while LN<RN:
            if LN&1:
                idxN.append(LN)
                LN+=1
            if RN&1:
                RN-=1
                idxN.append(RN)
            LN>>=1
            RN>>=1
        while LM<RM:
            if LM&1:
                idxM.append(LM)
                LM+=1
            if RM&1:
                RM-=1
                idxM.append(RM)
            LM>>=1
            RM>>=1
        v=self.e
        for i in idxN:
            for j in idxM:
                v=self.f(v,self.segment_tree[i][j])
        for i in idxN:
            for j in idxM:
                if v==self.f(v,self.segment_tree[i][j]):
                    break
            else:
                continue
            break
        while i<self.N:
            if self.segment_tree[i<<1][j]==v:
                i<<=1
            else:
                i<<=1
                i|=1
        while j<self.M:
            if self.segment_tree[i][j<<1]==v:
                j<<=1
            else:
                j<<=1
                j|=1
        return i,j

    def __str__(self):
        m=max(len(str(self.segment_tree[i][j])) for i in range(self.N,self.N*2) for j in range(self.M,self.M*2))
        return "\n".join(["["+", ".join(map(lambda s:" "*(m-len(str(s)))+str(s),self.segment_tree[i][self.M:]))+"]" for i in range(self.N,self.N*2)])

class Dual_Segment_Tree:
    def __init__(self,N,f_act,e_act,operate,lst):
        self.N=N
        self.f_act=f_act
        self.e_act=e_act
        self.operate=operate
        self.lst=[None]*self.N
        for i,x in enumerate(lst):
            self.lst[i]=x
        self.segment_tree_act=[self.e_act]*(self.N+self.N)

    def __getitem__(self,i):
        if type(i) is int:
            if -self.N<=i<0:
                i+=self.N*2
            elif 0<=i<self.N:
                i+=self.N
            else:
                raise IndexError("list index out of range")
            self.Propagate_Above(i)
            return self.Operate_At(i)
        else:
            a,b,c=i.start,i.stop,i.step
            if a==None or a<-self.N:
                a=0
            elif self.N<=a:
                a=self.N
            elif a<0:
                a+=self.N
            if b==None or self.N<=b:
                b=self.N
            elif b<-self.N:
                b=0
            elif b<0:
                b+=self.N
            return self.lst[slice(a,b,c)]

    def Operate_At(self,i):
        return self.operate(self.lst[i-self.N],self.segment_tree_act[i])

    def Propagate_At(self,i):
        self.segment_tree_act[i<<1]=self.f_act(self.segment_tree_act[i<<1],self.segment_tree_act[i])
        self.segment_tree_act[i<<1|1]=self.f_act(self.segment_tree_act[i<<1|1],self.segment_tree_act[i])
        self.segment_tree_act[i]=self.e_act

    def Propagate_Above(self,i):
        H=i.bit_length()-1
        for h in range(H,0,-1):
            self.Propagate_At(i>>h)

    def Operate_Range(self,a,L=None,R=None):
        if L==None:
            L=self.N
        else:
            L+=self.N
        if R==None:
            R=self.N*2
        else:
            R+=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.segment_tree_act[L]=self.f_act(self.segment_tree_act[L],a)
                L+=1
            if R&1:
                R-=1
                self.segment_tree_act[R]=self.f_act(self.segment_tree_act[R],a)
            L>>=1
            R>>=1

    def Update(self):
        for i in range(1,self.N):
            self.Propagate_At(i)
            self.segment_tree_act[i]=self.e_act

    def __str__(self):
        import copy
        segment_tree_act=copy.deepcopy(self.segment_tree_act)
        for i in range(1,self.N):
            segment_tree_act[i<<1]=self.f_act(segment_tree_act[i<<1],segment_tree_act[i])
            segment_tree_act[i<<1|1]=self.f_act(segment_tree_act[i<<1|1],segment_tree_act[i])
            segment_tree_act[i]=self.e_act
            segment_tree_act[i]=self.e_act
        return "["+", ".join(map(str,[self.operate(x,a) for x,a in zip(self.lst,segment_tree_act[self.N:])]))+"]"

class Lazy_Segment_Tree:
    def __init__(self,N,f,e,f_act,e_act,operate,lst=None):
        self.N=N
        self.f=f
        self.e=e
        self.f_act=f_act
        self.e_act=e_act
        self.operate=operate
        self.segment_tree=[self.e]*(self.N+self.N)
        self.segment_tree_act=[self.e_act]*(self.N+self.N)
        if lst!=None:
            for i,x in enumerate(lst):
                self.segment_tree[i+self.N]=x
            for i in range(self.N-1,0,-1):
                self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])
            self.segment_tree_act=[self.e_act]*(self.N+self.N)

    def __getitem__(self,i):
        if type(i) is int:
            if -self.N<=i<0:
                i+=self.N*2
            elif 0<=i<self.N:
                i+=self.N
            else:
                raise IndexError("list index out of range")
            self.Propagate_Above(i)
            self.Recalculate_Above(i)
            return self.Operate_At(i)
        else:
            a,b,c=i.start,i.stop,i.step
            if a==None or a<-self.N:
                a=self.N
            elif self.N<=a:
                a=self.N*2
            elif a<0:
                a+=self.N*2
            else:
                a+=self.N
            if b==None or self.N<=b:
                b=self.N*2
            elif b<-self.N:
                b=self.N
            elif b<0:
                b+=self.N*2
            else:
                b+=self.N
            return self.segment_tree[slice(a,b,c)]

    def __setitem__(self,i,x):
        if -self.N<=i<0:
            i+=self.N*2
        elif 0<=i<self.N:
            i+=self.N
        else:
            raise IndexError("list index out of range")
        self.Propagate_Above(i)
        self.segment_tree[i]=x
        self.segment_tree_act[i]=self.e_act
        self.Recalculate_Above(i)

    def Operate_At(self,i):
        return self.operate(self.segment_tree[i],self.segment_tree_act[i])

    def Propagate_At(self,i):
        self.segment_tree[i]=self.Operate_At(i)
        self.segment_tree_act[i<<1]=self.f_act(self.segment_tree_act[i<<1],self.segment_tree_act[i])
        self.segment_tree_act[i<<1|1]=self.f_act(self.segment_tree_act[i<<1|1],self.segment_tree_act[i])
        self.segment_tree_act[i]=self.e_act

    def Propagate_Above(self,i):
        H=i.bit_length()-1
        for h in range(H,0,-1):
            self.Propagate_At(i>>h)

    def Recalculate_Above(self,i):
        while i>1:
            i>>=1
            self.segment_tree[i]=self.f(self.Operate_At(i<<1),self.Operate_At(i<<1|1))

    def Build(self,lst):
        for i,x in enumerate(lst):
            self.segment_tree[i+self.N]=x
        for i in range(self.N-1,0,-1):
            self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])
        self.segment_tree_act=[self.e_act]*(self.N+self.N)

    def Fold(self,L=None,R=None):
        if L==None:
            L=self.N
        else:
            L+=self.N
        if R==None:
            R=self.N*2
        else:
            R+=self.N
        self.Propagate_Above(L//(L&-L))
        self.Propagate_Above(R//(R&-R)-1)
        vL=self.e
        vR=self.e
        while L<R:
            if L&1:
                vL=self.f(vL,self.Operate_At(L))
                L+=1
            if R&1:
                R-=1
                vR=self.f(self.Operate_At(R),vR)
            L>>=1
            R>>=1
        return self.f(vL,vR)

    def Fold_Index(self,L=None,R=None):
        if L==None:
            L=self.N
        else:
            L+=self.N
        if R==None:
            R=self.N*2
        else:
            R+=self.N
        if L==R:
            return None
        x=self.Fold(L-self.N,R-self.N)
        while L<R:
            if L&1:
                if self.segment_tree[L]==x:
                    i=L
                    break
                L+=1
            if R&1:
                R-=1
                if self.segment_tree[R]==x:
                    i=R
                    break
            L>>=1
            R>>=1
        while i<self.N:
            if self.segment_tree[i]==self.segment_tree[i<<1]:
                i<<=1
            else:
                i<<=1
                i|=1
        i-=self.N
        return i

    def Operate_Range(self,a,L=None,R=None):
        if L==None:
            L=self.N
        else:
            L+=self.N
        if R==None:
            R=self.N*2
        else:
            R+=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.segment_tree_act[L]=self.f_act(self.segment_tree_act[L],a)
                L+=1
            if R&1:
                R-=1
                self.segment_tree_act[R]=self.f_act(self.segment_tree_act[R],a)
            L>>=1
            R>>=1
        self.Recalculate_Above(L0)
        self.Recalculate_Above(R0)

    def Update(self):
        for i in range(1,self.N):
            self.Propagate_At(i)
        for i in range(self.N,self.N*2):
            self.segment_tree[i]=self.Operate_At(i)
            self.segment_tree_act[i]=self.e_act
        for i in range(self.N-1,0,-1):
            self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])

    def Bisect_Right(self,L=None,f=None):
        if L==self.N:
            return self.N
        if L==None:
            L=0
        L+=self.N
        self.Propagate_Above(L//(L&-L))
        self.Propagate_Above(self.N//(self.N&-self.N)-1)
        l,r=L,self.N*2
        vl=self.e
        vr=self.e
        while l<r:
            if l&1:
                vl=self.f(vl,self.Operate_At(l))
                l+=1
            if r&1:
                r-=1
                vr=self.f(self.Operate_At(r),vr)
            l>>=1
            r>>=1
        if f(self.f(vl,vr)):
            return self.N
        v=self.e
        self.Propagate_Above(L)
        while True:
            while L%2==0:
                L>>=1
            vv=self.f(v,self.Operate_At(L))
            if f(vv):
                v=vv
                L+=1
            else:
                while L<self.N:
                    self.Propagate_At(L)
                    L<<=1
                    vv=self.f(v,self.Operate_At(L))
                    if f(vv):
                        v=vv
                        L+=1
                return L-self.N

    def Bisect_Left(self,R=None,f=None):
        if R==0:
            return 0
        if R==None:
            R=self.N
        R+=self.N
        self.Propagate_Above(self.N//(self.N&-self.N))
        self.Propagate_Above(R//(R&-R)-1)
        vl=self.e
        vr=self.e
        l,r=self.N,R
        while l<r:
            if l&1:
                vl=self.f(vl,self.Operate_At(l))
                l+=1
            if r&1:
                r-=1
                vr=self.f(self.Operate_At(r),vr)
            l>>=1
            r>>=1
        if f(self.f(vl,vr)):
            return 0
        v=self.e
        self.Propagate_Above(R-1)
        while True:
            R-=1
            while R>1 and R%2:
                R>>=1
            vv=self.f(self.Operate_At(R),v)
            if f(vv):
                v=vv
            else:
                while R<self.N:
                    self.Propagate_At(R)
                    R=(R<<1)|1
                    vv=self.f(self.Operate_At(R),v)
                    if f(vv):
                        v=vv
                        R-=1
                return R+1-self.N

    def __str__(self):
        import copy
        segment_tree=copy.deepcopy(self.segment_tree)
        segment_tree_act=copy.deepcopy(self.segment_tree_act)
        for i in range(1,self.N):
            segment_tree[i]=self.operate(segment_tree[i],segment_tree_act[i])
            segment_tree_act[i<<1]=self.f_act(segment_tree_act[i<<1],segment_tree_act[i])
            segment_tree_act[i<<1|1]=self.f_act(segment_tree_act[i<<1|1],segment_tree_act[i])
            segment_tree_act[i]=self.e_act
        for i in range(self.N,self.N*2):
            segment_tree[i]=self.operate(segment_tree[i],segment_tree_act[i])
            segment_tree_act[i]=self.e_act
        for i in range(self.N-1,0,-1):
            segment_tree[i]=self.f(segment_tree[i<<1],segment_tree[i<<1|1])
        return "["+", ".join(map(str,[self.operate(x,a) for x,a in zip(segment_tree[self.N:],segment_tree_act[self.N:])]))+"]"

N,M,A=map(int,readline().split())
P=[[] for r in range(N+1)]
for m in range(M):
    l,r,p=map(int,readline().split())
    l-=1
    P[r].append([l,p])
ans=0
inf=1<<60
dp=Segment_Tree(N+1,max,-inf,[-A]*(N+1))
dp[0]=0
for r in range(N+1):
    dp[r]=max(dp[r],dp.Fold(0,r)-A)
    for l,p in P[r]:
        dp[r]=max(dp[r],dp[l]+p+(-A if r<N else 0))
    ans=max(ans,dp[r])
print(ans)
yukicoder

結果

テストケース

ソースコード
