結果
問題 | No.844 split game |
ユーザー | vwxyz |
提出日時 | 2022-10-26 12:30:16 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 22,369 bytes |
コンパイル時間 | 87 ms |
コンパイル使用メモリ | 15,232 KB |
実行使用メモリ | 39,624 KB |
最終ジャッジ日時 | 2024-07-04 02:59:38 |
合計ジャッジ時間 | 22,781 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,008 ms
31,196 KB |
testcase_01 | AC | 1,892 ms
29,068 KB |
testcase_02 | AC | 1,671 ms
32,256 KB |
testcase_03 | AC | 1,980 ms
32,512 KB |
testcase_04 | AC | 880 ms
22,764 KB |
testcase_05 | TLE | - |
testcase_06 | AC | 849 ms
22,456 KB |
testcase_07 | AC | 1,555 ms
26,256 KB |
testcase_08 | AC | 584 ms
18,688 KB |
testcase_09 | AC | 987 ms
26,920 KB |
testcase_10 | TLE | - |
testcase_11 | TLE | - |
testcase_12 | AC | 1,010 ms
26,496 KB |
testcase_13 | AC | 692 ms
22,144 KB |
testcase_14 | AC | 1,571 ms
27,384 KB |
testcase_15 | TLE | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
testcase_36 | -- | - |
testcase_37 | -- | - |
testcase_38 | -- | - |
testcase_39 | -- | - |
testcase_40 | -- | - |
testcase_41 | -- | - |
testcase_42 | -- | - |
testcase_43 | -- | - |
testcase_44 | -- | - |
testcase_45 | -- | - |
testcase_46 | -- | - |
testcase_47 | -- | - |
testcase_48 | -- | - |
testcase_49 | -- | - |
testcase_50 | -- | - |
testcase_51 | -- | - |
testcase_52 | -- | - |
testcase_53 | -- | - |
testcase_54 | -- | - |
testcase_55 | -- | - |
testcase_56 | -- | - |
testcase_57 | -- | - |
testcase_58 | -- | - |
testcase_59 | -- | - |
ソースコード
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)