#972016 (PyPy3) No.855 ヘビの日光浴

提出ソース

結果

問題	No.855 ヘビの日光浴
ユーザー	vwxyz
提出日時	2024-04-13 10:55:43
言語	PyPy3 (7.3.15)
結果	WA
実行時間	-
コード長	7,224 bytes
コンパイル時間	387 ms
コンパイル使用メモリ	81,792 KB
実行使用メモリ	131,176 KB
最終ジャッジ日時	2024-10-02 23:59:44
合計ジャッジ時間	23,994 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	50 ms 55,040 KB
testcase_01	AC	50 ms 55,424 KB
testcase_02	AC	51 ms 55,168 KB
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	AC	54 ms 56,192 KB
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	AC	51 ms 55,680 KB
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	AC	51 ms 55,552 KB
testcase_31	WA	-
testcase_32	AC	53 ms 55,808 KB
testcase_33	WA	-
testcase_34	WA	-
testcase_35	WA	-
testcase_36	WA	-
testcase_37	WA	-
testcase_38	WA	-
testcase_39	WA	-
testcase_40	WA	-
testcase_41	WA	-
testcase_42	WA	-
testcase_43	WA	-
testcase_44	WA	-
testcase_45	WA	-
testcase_46	WA	-
testcase_47	WA	-
testcase_48	WA	-
testcase_49	WA	-
testcase_50	WA	-
testcase_51	WA	-
testcase_52	WA	-
testcase_53	WA	-
testcase_54	WA	-
testcase_55	AC	52 ms 55,680 KB
testcase_56	WA	-
testcase_57	WA	-
testcase_58	WA	-
testcase_59	WA	-
testcase_60	WA	-
testcase_61	WA	-
testcase_62	WA	-
testcase_63	AC	50 ms 55,424 KB
testcase_64	WA	-
testcase_65	WA	-
testcase_66	AC	54 ms 55,936 KB
testcase_67	AC	50 ms 55,296 KB
testcase_68	AC	51 ms 55,808 KB
testcase_69	AC	53 ms 55,808 KB
testcase_70	AC	51 ms 55,552 KB
testcase_71	WA	-
testcase_72	WA	-
testcase_73	WA	-
testcase_74	WA	-
testcase_75	WA	-
testcase_76	WA	-
testcase_77	WA	-
testcase_78	WA	-
testcase_79	WA	-
testcase_80	WA	-
testcase_81	WA	-
testcase_82	WA	-
testcase_83	WA	-
testcase_84	WA	-
testcase_85	WA	-
testcase_86	WA	-
testcase_87	WA	-
testcase_88	WA	-
testcase_89	WA	-
testcase_90	WA	-
testcase_91	WA	-
testcase_92	WA	-
testcase_93	WA	-
testcase_94	AC	369 ms 116,192 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

from collections import defaultdict

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:]))+"]"

def Compress(lst):
    decomp=sorted(list(set(lst)))
    comp={x:i for i,x in enumerate(decomp)}
    return comp,decomp

W,H,N=map(int,input().split())
XYL=[]
X,Y=[],[]
for i in range(N):
    x,y,l=map(int,input().split())
    if x in (0,H+1):
        Y.append(y)
    else:
        X.append(x)
    XYL.append((x,y,l))
compX,decompX=Compress(X)
compY,decompY=Compress(Y)
leX=len(compX)
leY=len(compY)
inf=1<<60
STX0=Segment_Tree(leX,max,-inf,[0]*leX)
STX1=Segment_Tree(leX,max,-inf,[0]*leX)
STY0=Segment_Tree(leY,max,-inf,[0]*leY)
STY1=Segment_Tree(leY,max,-inf,[0]*leY)
for x,y,l in XYL:
    if x==0:
        j=compY[y]
        l+=STY0[j]
        r0=STX0.Bisect_Right(0,lambda ma:ma<=y-1)
        r1=STX1.Bisect_Right(0,lambda ma:ma<=W-y)
        if r0<r1 and decompX[r0]<l:
            STX0[r0]=0
            STY0[j]=0
        elif r1<r0 and decompX[r1]<l:
            STX1[r1]=0
            STY0[j]=0
        elif l<H+1:
            STY0[j]=l
    elif x==H+1:
        j=compY[y]
        l+=STY1[j]
        l0=STX0.Bisect_Left(leX,lambda ma:ma<=y-1)
        l1=STX1.Bisect_Left(leX,lambda ma:ma<=W-y)
        if l0>l1 and H-decompX[l0-1]<l:
            STX0[l0-1]=0
            STY1[j]=0
        elif l1>l0 and H-decompX[l1-1]<l:
            STX1[l1-1]=0
            STY1[j]=0
        elif l<H+1:
            STY1[j]=l
    elif y==0:
        i=compX[x]
        l+=STX0[i]
        r0=STY0.Bisect_Right(0,lambda ma:ma<=x-1)
        r1=STY1.Bisect_Right(0,lambda ma:ma<=H-x)
        if r0<r1 and decompY[r0]<l:
            STY0[r0]=0
            STX0[i]=0
        elif r1<r0 and decompY[r1]<l:
            STY1[r1]=0
            STX0[i]=0
        elif l<W+1:
            STX0[i]=l
    elif y==W+1:
        i=compX[x]
        l+=STX1[i]
        l0=STY0.Bisect_Left(leY,lambda ma:ma<=x-1)
        l1=STY1.Bisect_Left(leY,lambda ma:ma<=H-x)
        if l0>l1 and W-decompY[l0-1]:
            STY0[l0-1]=0
            STX1[i]=0
        elif l1>l0 and W-decompY[l1-1]:
            STY1[l1-1]=0
            STX1[i]=0
        elif l<W+1:
            STX1[i]=l
ans=sum(STX0[x]+STX1[x] for x in range(leX))+sum(STY0[y]+STY1[y] for y in range(leY))
print(ans)

yukicoder

結果

テストケース

ソースコード