提出 #63837482

ソースコード 拡げる

class LazySegTreeFast:
    def __init__(self,N,A,op,mapping,composition,e) -> None:
        #N:数列の長さ
        #A:数列の初期状態
        #op:区間で答えたいもの
        #mapping:更新方法
        #composition:mappingの合成
        #e:∀a,op(a,e)=aとなる単位元e
        size=1
        log_size=1
        while size<N:
            size*=2
            log_size+=1
        #size:セグ木の横の大きさ
        #log_size:セグ木の深さ
        self.size=size
        self.log_size=log_size
        self.op=op
        self.mapping=mapping
        self.composition=composition
        self.e=e
        self.tree=[e]*(2*size)
        self.lazy=[None]*(2*size)
        
        #A[i]の長さ
        self.long=[0]*(2*size)
        #最下層の初期化
        for i in range(N):
            self.tree[size+i]=A[i]
            self.long[size+i]=1
            # self.lazy[size+i]=A[i]
        #最下層以外の初期化
        for i in range((size-1),0,-1):
            self.tree[i]=op(self.tree[2*i],self.tree[2*i+1])
            self.long[i]=self.long[2*i]+self.long[2*i+1]
        #treeの0番目の値は使用しない(欠番)
    
    #seg_treeを深さ順に出力
    #時間計算量O(N)
    def print_seg_tree(self):
        for i in range(self.log_size):
            print(self.tree[2**i:2**(i+1)])

    #lazyを深さ順に出力
    #時間計算量O(N)
    def print_lazy(self):
        for i in range(self.log_size):
            print(self.lazy[2**i:2**(i+1)])
    
    # #Aのi番目(0-indexed)の要素を取得
    # #時間計算量O(1)
    # def get(self,i):
    #     return self.tree[self.size+i]
    
    #A[i]のlazyを伝播する
    # def lazy_eval(self,i):
    #     if(self.lazy[i]==None):
    #         return
    #     #treeの値を更新する
    #     self.tree[i]=self.mapping(self.tree[i],self.lazy[i])
    #     #最下層でない場合
    #     if(self.size>i):
    #         self.lazy[2*i]=self.composition(self.lazy[2*i],self.lazy[i])
    #         self.lazy[2*i+1]=self.composition(self.lazy[2*i+1],self.lazy[i])
    #     #lazyの値を戻す
    #     self.lazy[i]=None

    #[l,r)から伝播するAのindexを昇順で返す
    def root(self,l,r):
        L = l + self.size
        R = r + self.size
        lm = (L // (L & -L)) >> 1
        rm = (R // (R & -R)) >> 1
        while L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            L >>= 1; R >>= 1
        while L:
            yield L
            L >>= 1
    
    def propagates(self,*inds):
        for i in reversed(inds):
            if(self.lazy[i]==None):
                continue
            #最下層でない場合
            if(self.size>i):
                self.lazy[2*i]=self.composition(self.lazy[2*i],self.lazy[i])
                self.tree[2*i]=self.mapping(self.tree[2*i],self.lazy[i],self.long[2*i])
                self.lazy[2*i+1]=self.composition(self.lazy[2*i+1],self.lazy[i])
                self.tree[2*i+1]=self.mapping(self.tree[2*i+1],self.lazy[i],self.long[2*i+1])
                
            self.lazy[i]=None
    
    #Aの[l,r)をmapping(A[i],x)で更新
    #時間計算量O(logN)
    def update(self,l,r,x):
        
        *inds,=self.root(l,r)
        # print(inds,"!")
        # self.propagates(*inds)
        
        # self.print_seg_tree()
        # self.print_lazy()
        # print()
        l+=self.size
        r+=self.size
        while l<r:
            # print(l,r)
            if(l%2==1):
                # print(l,"l")
                self.lazy[l]=self.composition(self.lazy[l],x)
                self.tree[l]=self.mapping(self.tree[l],x,self.long[l])
                l+=1
            if(r%2==1):
                # print(r,"r")
                self.lazy[r-1]=self.composition(self.lazy[r-1],x)
                self.tree[r-1]=self.mapping(self.tree[r-1],x,self.long[r-1])
                r-=1
            l=l//2
            r=r//2
        
        # self.print_seg_tree()
        # self.print_lazy()
        # print()
        for i in inds:
            self.tree[i]=self.op(self.tree[2*i],self.tree[2*i+1])
            if(self.lazy[i]!=None):
                self.tree[i]=self.mapping(self.tree[i],self.lazy[i],self.long[i])
    
    #Aの[l,r)に対するop(A[l],op(A[l+1],...op(A[r-1])...))を取得(0-indexed)
    def range_op(self,l,r):
        
        *inds,=self.root(l,r)
        
        self.propagates(*inds)
        
        l+=self.size
        r+=self.size
        left_result=self.e
        right_result=self.e
        while l<r:
            if(l%2==1):
                left_result=self.op(left_result,self.tree[l])
                l+=1
            if(r%2==1):
                right_result=self.op(right_result,self.tree[r-1])
                r-=1
            l=l//2
            r=r//2
        return self.op(left_result,right_result)


def solve2(N, A):
    Lback = [0] * (N - 2)
    Lfront = [0] * (N - 2)
    S = set([A[-1]])
    for i in range(N - 1, 1, -1):
        Lback[i - 2] += len(S)
        S.add(A[i - 1])

    S = set([A[0]])
    for i in range(N - 2):
        Lfront[i] += len(S)
        S.add(A[1 + i])

    def LSmap(a,b,l):
        return a+b
    def LScomp(a,b):
        if(a==None):
            return b
        else:
            return a+b
    LST = LazySegTreeFast(N, [0] * N, max, LSmap, LScomp, 0)
    Last = [-1] * (N + 1)
    cnt = 0
    ans = 0
    for i in range(N - 1):

        if(Last[A[i]] == -1):
            Last[A[i]] = i
            cnt += 1
        else:
            LST.update(Last[A[i]] + 1, i + 1, 1)
            Last[A[i]] = i
        if(i >= 1):
            #print(Last, cnt, LST.range_op(0, N), Lback[i - 1])
            ans = max(ans, cnt + LST.range_op(0, N) + Lback[i - 1])
        # else:
        #     print(Last, cnt, LST.range_op(0, N))
    return ans

def gutyoku(N, A):
    ans = 0
    for i in range(N - 1):
        for j in range(i + 1, N - 1):
            S = [set() for _ in range(3)]
            for x in range(N):
                if(x <= i):
                    S[0].add(A[x])
                elif(x <= j):
                    S[1].add(A[x])
                else:
                    S[2].add(A[x])
            ans = max(ans, len(S[0]) + len(S[1]) + len(S[2]))
            #print(i, j, ans)
    return ans
# import random
# random.seed(51)
# while True:
#     N = random.randint(3, 20)
#     print(N)
#     A = []
#     for i in range(N):
#         A.append(random.randint(1, N))
#     ans1 = solve2(N, A)
#     ans2 = gutyoku(N, A)
#     if(ans1 != ans2):
#         print(N)
#         print(*A)
#         print(ans1, ans2)
#         break
N = int(input())
A = list(map(int, input().split()))
# print(gutyoku(N, A))
print(solve2(N, A))

提出情報

提出日時
問題 F - Variety Split Hard
ユーザ Koi51
言語 Python (PyPy 3.10-v7.3.12)
得点 550
コード長 6988 Byte
結果 AC
実行時間 1058 ms
メモリ 186020 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 550 / 550
結果
AC × 2
AC × 44
セット名 テストケース
Sample 00_sample_00.txt, 00_sample_01.txt
All 00_sample_00.txt, 00_sample_01.txt, 01_test_00.txt, 01_test_01.txt, 01_test_02.txt, 01_test_03.txt, 01_test_04.txt, 01_test_05.txt, 01_test_06.txt, 01_test_07.txt, 01_test_08.txt, 01_test_09.txt, 01_test_10.txt, 01_test_11.txt, 01_test_12.txt, 01_test_13.txt, 01_test_14.txt, 01_test_15.txt, 01_test_16.txt, 01_test_17.txt, 01_test_18.txt, 01_test_19.txt, 01_test_20.txt, 01_test_21.txt, 01_test_22.txt, 01_test_23.txt, 01_test_24.txt, 01_test_25.txt, 01_test_26.txt, 01_test_27.txt, 01_test_28.txt, 01_test_29.txt, 01_test_30.txt, 01_test_31.txt, 01_test_32.txt, 01_test_33.txt, 01_test_34.txt, 01_test_35.txt, 01_test_36.txt, 01_test_37.txt, 01_test_38.txt, 01_test_39.txt, 01_test_40.txt, 01_test_41.txt
ケース名 結果 実行時間 メモリ
00_sample_00.txt AC 57 ms 76412 KiB
00_sample_01.txt AC 57 ms 76572 KiB
01_test_00.txt AC 81 ms 82576 KiB
01_test_01.txt AC 74 ms 81680 KiB
01_test_02.txt AC 91 ms 83440 KiB
01_test_03.txt AC 84 ms 82480 KiB
01_test_04.txt AC 77 ms 81928 KiB
01_test_05.txt AC 304 ms 116428 KiB
01_test_06.txt AC 813 ms 167768 KiB
01_test_07.txt AC 590 ms 168312 KiB
01_test_08.txt AC 870 ms 167740 KiB
01_test_09.txt AC 627 ms 168388 KiB
01_test_10.txt AC 850 ms 167848 KiB
01_test_11.txt AC 334 ms 123984 KiB
01_test_12.txt AC 804 ms 167656 KiB
01_test_13.txt AC 691 ms 186020 KiB
01_test_14.txt AC 839 ms 168200 KiB
01_test_15.txt AC 1058 ms 143888 KiB
01_test_16.txt AC 544 ms 143768 KiB
01_test_17.txt AC 1007 ms 151084 KiB
01_test_18.txt AC 506 ms 151396 KiB
01_test_19.txt AC 1002 ms 155232 KiB
01_test_20.txt AC 517 ms 155160 KiB
01_test_21.txt AC 872 ms 160140 KiB
01_test_22.txt AC 484 ms 159988 KiB
01_test_23.txt AC 805 ms 164676 KiB
01_test_24.txt AC 481 ms 164780 KiB
01_test_25.txt AC 524 ms 162644 KiB
01_test_26.txt AC 540 ms 164480 KiB
01_test_27.txt AC 536 ms 164332 KiB
01_test_28.txt AC 534 ms 164780 KiB
01_test_29.txt AC 528 ms 163580 KiB
01_test_30.txt AC 538 ms 163920 KiB
01_test_31.txt AC 350 ms 185216 KiB
01_test_32.txt AC 382 ms 185396 KiB
01_test_33.txt AC 57 ms 76676 KiB
01_test_34.txt AC 57 ms 76296 KiB
01_test_35.txt AC 444 ms 167836 KiB
01_test_36.txt AC 531 ms 140164 KiB
01_test_37.txt AC 516 ms 136472 KiB
01_test_38.txt AC 355 ms 185412 KiB
01_test_39.txt AC 351 ms 185392 KiB
01_test_40.txt AC 352 ms 185224 KiB
01_test_41.txt AC 354 ms 185312 KiB