#810343 (PyPy3) No.515 典型LCP

提出ソース
結果

問題	No.515 典型LCP
ユーザー	vwxyz
提出日時	2022-10-23 19:21:22
言語	PyPy3 (7.3.15)
結果	TLE (最新) AC (最初)
実行時間	-
コード長	14,887 bytes
コンパイル時間	532 ms
コンパイル使用メモリ	86,916 KB
実行使用メモリ	129,372 KB
最終ジャッジ日時	2023-09-15 04:55:18
合計ジャッジ時間	10,654 ms
ジャッジサーバーID （参考情報）	judge14 / judge13
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	TLE	-
testcase_01	AC	932 ms 129,372 KB
testcase_02	AC	501 ms 98,604 KB
testcase_03	AC	280 ms 95,420 KB
testcase_04	AC	276 ms 95,752 KB
testcase_05	AC	391 ms 96,688 KB
testcase_06	AC	394 ms 96,876 KB
testcase_07	AC	389 ms 96,876 KB
testcase_08	AC	447 ms 96,816 KB
testcase_09	AC	424 ms 98,292 KB
testcase_10	AC	434 ms 98,588 KB
testcase_11	AC	432 ms 98,436 KB
testcase_12	AC	431 ms 98,968 KB
testcase_13	AC	402 ms 98,044 KB
testcase_14	AC	323 ms 98,216 KB
testcase_15	AC	376 ms 96,504 KB
testcase_16	AC	370 ms 96,700 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

def SA_IS(lst,compressed=False):
    N=len(lst)
    if not compressed:
        decomp=sorted(list(set(lst)))
        comp={x:i for i,x in enumerate(decomp)}
        lst=[comp[s]+1 for s in lst]+[0]
    else:
        lst=[s+1 for s in lst]+[0]

    def induced_sort(N,lst,type,LMS,bucket_count,sorted_LMS_index=None):
        buckets_left=[[] for b in range(bucket_count)]
        buckets_right=[[] for b in range(bucket_count)]
        if sorted_LMS_index==None:
            for i in LMS:
                buckets_right[lst[i]].append(i)
        else:
            for i in sorted_LMS_index[::-1]:
                buckets_right[lst[LMS[i]]].append(LMS[i])
        for b in range(bucket_count):
            for i in buckets_left[b]:
                if i and type[i-1]=="L":
                    buckets_left[lst[i-1]].append(i-1)
            for i in buckets_right[b][::-1]:
                if i and type[i-1]=="L":
                    buckets_left[lst[i-1]].append(i-1)
            buckets_right[b]=[]
        for b in range(bucket_count-1,-1,-1):
            for i in buckets_right[b]:
                if i and type[i-1]=="S":
                    buckets_right[lst[i-1]].append(i-1)
            for i in buckets_left[b][::-1]:
                if i and type[i-1]=="S":
                    buckets_right[lst[i-1]].append(i-1)
        suffix_array=[N]
        for b in range(1,bucket_count):
            suffix_array+=buckets_left[b]+buckets_right[b][::-1]
        return suffix_array
    
    stack=[]
    while N>=1:
        type=[None]*(N+1)
        type[N]="S"
        for i in range(N-1,-1,-1):
            if lst[i]<lst[i+1]:
                type[i]="S"
            elif lst[i]>lst[i+1]:
                type[i]="L"
            else:
                type[i]=type[i+1]
        LMS=[i for i in range(1,N) if type[i-1]=="L" and type[i]=="S"]+[N]
        bucket_count=max(lst)+1
        stack.append((N,lst,type,LMS,bucket_count))
        suffix_array=induced_sort(N,lst,type,LMS,bucket_count)
        LMS_substring=[None]*(N+1)
        for i in range(len(LMS)-1):
            LMS_substring[LMS[i]]=lst[LMS[i]:LMS[i+1]]
        LMS_substring[N]=lst[N:N+1]
        num=0
        prev=[0]
        for i in suffix_array:
            if LMS_substring[i]!=None:
                if prev!=LMS_substring[i]:
                    prev=LMS_substring[i]
                    num+=1
                LMS_substring[i]=num
        lst=[LMS_substring[i] for i in LMS]
        N=len(lst)-1
    sorted_LMS_index=[0]
    for N,lst,type,LMS,bucket_count in stack[::-1]:
        suffix_array=induced_sort(N,lst,type,LMS,bucket_count,sorted_LMS_index)
        sorted_LMS_index=suffix_array
    suffix_array=suffix_array[1:]
    return suffix_array

class Rolling_Hash:
    def __init__(self,lst,base,mod):
        assert math.gcd(base,mod)==1
        self.len=len(lst)
        self.base=base
        self.mod=mod
        self.rolling_hash=[None]*(self.len+1)
        self.rolling_hash[0]=0
        x=1
        for i in range(1,self.len+1):
            self.rolling_hash[i]=self.rolling_hash[i-1]+x*lst[i-1]
            self.rolling_hash[i]%=self.mod
            x*=self.base
            x%=self.mod
        x=MOD(self.mod).Pow(x,-1)
        self.base_reverse=[None]*(self.len+1)
        self.base_reverse[self.len]=x
        for i in range(self.len-1,-1,-1):
            self.base_reverse[i]=self.base_reverse[i+1]*self.base%self.mod

    def __getitem__(self,i):
        if type(i)==int:
            a,b=i,i+1
        else:
            a,b=i.start,i.stop
            if a==None or a<-self.len:
                a=0
            elif self.len<=a:
                a=self.len
            elif a<0:
                a+=self.len
            if b==None or self.len<=b:
                b=self.len
            elif b<-self.len:
                b=0
            elif b<0:
                b+=self.len
        return (self.rolling_hash[b]-self.rolling_hash[a])*self.base_reverse[a]%self.mod

    def __len__(self):
        return self.len

def Extended_Euclid(n,m):
    stack=[]
    while m:
        stack.append((n,m))
        n,m=m,n%m
    if n>=0:
        x,y=1,0
    else:
        x,y=-1,0
    for i in range(len(stack)-1,-1,-1):
        n,m=stack[i]
        x,y=y,x-(n//m)*y
    return x,y

class MOD:
    def __init__(self,p,e=None):
        self.p=p
        self.e=e
        if self.e==None:
            self.mod=self.p
        else:
            self.mod=self.p**self.e

    def Pow(self,a,n):
        a%=self.mod
        if n>=0:
            return pow(a,n,self.mod)
        else:
            assert math.gcd(a,self.mod)==1
            x=Extended_Euclid(a,self.mod)[0]
            return pow(x,-n,self.mod)

    def Build_Fact(self,N):
        assert N>=0
        self.factorial=[1]
        if self.e==None:
            for i in range(1,N+1):
                self.factorial.append(self.factorial[-1]*i%self.mod)
        else:
            self.cnt=[0]*(N+1)
            for i in range(1,N+1):
                self.cnt[i]=self.cnt[i-1]
                ii=i
                while ii%self.p==0:
                    ii//=self.p
                    self.cnt[i]+=1
                self.factorial.append(self.factorial[-1]*ii%self.mod)
        self.factorial_inve=[None]*(N+1)
        self.factorial_inve[-1]=self.Pow(self.factorial[-1],-1)
        for i in range(N-1,-1,-1):
            ii=i+1
            while ii%self.p==0:
                ii//=self.p
            self.factorial_inve[i]=(self.factorial_inve[i+1]*ii)%self.mod

    def Fact(self,N):
        if N<0:
            return 0
        retu=self.factorial[N]
        if self.e!=None and self.cnt[N]:
            retu*=pow(self.p,self.cnt[N],self.mod)%self.mod
            retu%=self.mod
        return retu

    def Fact_Inve(self,N):
        if self.e!=None and self.cnt[N]:
            return None
        return self.factorial_inve[N]

    def Comb(self,N,K,divisible_count=False):
        if K<0 or K>N:
            return 0
        retu=self.factorial[N]*self.factorial_inve[K]%self.mod*self.factorial_inve[N-K]%self.mod
        if self.e!=None:
            cnt=self.cnt[N]-self.cnt[N-K]-self.cnt[K]
            if divisible_count:
                return retu,cnt
            else:
                retu*=pow(self.p,cnt,self.mod)
                retu%=self.mod
        return retu

def Bisect_Int(ok,ng,is_ok):
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if is_ok(mid):
            ok=mid
        else:
            ng=mid
    return ok

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 Path_Doubling:
    def __init__(self,N,permutation,lst=None,f=None,e=None):
        self.N=N
        self.permutation=permutation
        self.lst=lst
        self.f=f
        self.e=e

    def Build_Next(self,K=None):
        if K==None:
            K=self.N
        self.k=K.bit_length()
        self.permutation_doubling=[[self.permutation[n]] for n in range(self.N)]
        if self.lst!=None:
            self.doubling=[[self.lst[n]] for n in range(self.N)]
        for i in range(1,self.k):
            for n in range(self.N):
                self.permutation_doubling[n].append(self.permutation_doubling[self.permutation_doubling[n][i-1]][i-1])
                if self.f!=None:
                    self.doubling[n].append(self.f(self.doubling[n][i-1],self.doubling[self.permutation_doubling[n][i-1]][i-1]))

    def Permutation_Doubling(self,N,K):
        if K<0:
            return N
        for i in range(self.k):
            if K>>i&1:
                N=self.permutation_doubling[N][i]
        return N

    def Doubling(self,N,K):
        if K<0:
            return self.e
        retu=self.e
        for i in range(self.k):
            if K>>i&1:
                retu=self.f(retu,self.doubling[N][i])
                N=self.permutation_doubling[N][i]
        return retu

class Sparse_Table:
    def __init__(self,N,f,e,lst):
        self.N=N
        self.f=f
        self.e=e
        self.n=N.bit_length()
        self.dp=[[None]*(self.N-(1<<n)+1) for n in range(self.n)]
        if self.n:
            for i in range(self.N):
                self.dp[0][i]=lst[i]
            for n in range(1,self.n):
                for i in range(self.N-(1<<n)+1):
                    self.dp[n][i]=self.f(self.dp[n-1][i],self.dp[n-1][i+(1<<n-1)])

    def Fold(self,L=None,R=None):
        if L==None:
            L=0
        if R==None:
            R=self.N
        if L==R:
            return self.e
        n=(R-L).bit_length()-1
        return self.f(self.dp[n][L],self.dp[n][R-(1<<n)])

from operator import itemgetter
N=int(readline())
S=[readline().rstrip() for n in range(N)]
S=sorted(list(enumerate(S)),key=itemgetter(1))
idx=[None]*N
for i in range(N):
    idx[S[i][0]]=i
    S[i]=S[i][1]
base=random.randint(1<<50,1<<51)
mod=(1<<61)-1
LCP=[0]*(N-1)
for i in range(N-1):
    for a,b in zip(S[i],S[i+1]):
        if a==b:
            LCP[i]+=1
        else:
            break
ans=0
inf=1<<30
LCP=Sparse_Table(N-1,min,inf,LCP)
M,x,d=map(int,readline().split())
for k in range(1,M+1):
    i,j=(x//(N-1)),(x%(N-1))
    if i>j:
        i,j=j,i
    else:
        j+=1
    x=(x+d)%(N*(N-1))
    i,j=idx[i],idx[j]
    if i>j:
        i,j=j,i
    ans+=LCP.Fold(i,j)
print(ans)
yukicoder

結果

テストケース

ソースコード
