結果

問題 No.2549 Paint Eggs
ユーザー lloyzlloyz
提出日時 2023-12-11 02:53:38
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 388 ms / 2,000 ms
コード長 4,250 bytes
コンパイル時間 327 ms
コンパイル使用メモリ 82,404 KB
実行使用メモリ 118,692 KB
最終ジャッジ日時 2024-09-27 04:17:32
合計ジャッジ時間 15,966 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 56 ms
66,432 KB
testcase_01 AC 56 ms
67,712 KB
testcase_02 AC 52 ms
64,512 KB
testcase_03 AC 63 ms
71,680 KB
testcase_04 AC 65 ms
71,296 KB
testcase_05 AC 59 ms
67,968 KB
testcase_06 AC 68 ms
72,064 KB
testcase_07 AC 73 ms
74,532 KB
testcase_08 AC 54 ms
64,512 KB
testcase_09 AC 67 ms
71,936 KB
testcase_10 AC 292 ms
108,708 KB
testcase_11 AC 245 ms
118,692 KB
testcase_12 AC 275 ms
102,400 KB
testcase_13 AC 283 ms
104,572 KB
testcase_14 AC 191 ms
101,892 KB
testcase_15 AC 104 ms
77,696 KB
testcase_16 AC 276 ms
104,152 KB
testcase_17 AC 239 ms
102,144 KB
testcase_18 AC 204 ms
101,376 KB
testcase_19 AC 247 ms
100,480 KB
testcase_20 AC 343 ms
115,256 KB
testcase_21 AC 342 ms
114,572 KB
testcase_22 AC 364 ms
115,528 KB
testcase_23 AC 361 ms
115,020 KB
testcase_24 AC 368 ms
115,460 KB
testcase_25 AC 300 ms
115,584 KB
testcase_26 AC 315 ms
114,700 KB
testcase_27 AC 325 ms
115,252 KB
testcase_28 AC 368 ms
114,704 KB
testcase_29 AC 328 ms
114,968 KB
testcase_30 AC 370 ms
115,192 KB
testcase_31 AC 336 ms
115,592 KB
testcase_32 AC 348 ms
115,464 KB
testcase_33 AC 330 ms
115,728 KB
testcase_34 AC 325 ms
115,208 KB
testcase_35 AC 388 ms
115,196 KB
testcase_36 AC 365 ms
114,828 KB
testcase_37 AC 340 ms
115,328 KB
testcase_38 AC 322 ms
115,364 KB
testcase_39 AC 341 ms
115,592 KB
testcase_40 AC 380 ms
115,588 KB
testcase_41 AC 364 ms
114,960 KB
testcase_42 AC 372 ms
115,312 KB
testcase_43 AC 366 ms
114,700 KB
testcase_44 AC 358 ms
114,976 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class SegmentTree:

    __all__ = ['setval', 'pointupdate', 'segquery', 'segsearch_right', 'pointgetval']

    def __init__(self, n=10**6, idetify_elt=-10**9, func=max):
        assert (func(idetify_elt, idetify_elt) == idetify_elt)
        self._n = n
        self._seg_length_half = 2**(n-1).bit_length()
        self._idetify_elt = idetify_elt
        self._seg = [idetify_elt]*(2*self._seg_length_half)
        self._func = func

    def setval(self, x_list):
        '''Set value : A = x_list'''
        assert (len(x_list) == self._n)
        # Set value at the bottom
        for i in range(self._n):
            self._seg[i+self._seg_length_half-1] = x_list[i]    
        # Build value
        for i in range(self._seg_length_half-2, -1, -1):
            self._seg[i] = self._func(self._seg[2*i+1], self._seg[2*i+2])
    
    def pointupdate(self, k, x):
        '''Update : A[k] = x '''
        pos = k + self._seg_length_half - 1
        # Set value at k-th
        self._seg[pos] = x
        # Build bottom-up
        while pos:
            pos = (pos-1)//2
            self._seg[pos] = self._func(self._seg[pos*2+1], self._seg[pos*2+2])
    
    def pointgetval(self, k):
        ''' Return A[k] '''
        return self._seg[k + self._seg_length_half - 1]

    def segquery(self, left, right):
        ''' Return func(A[left], ... , A[right-1]) '''
        # if not left < right
        if right <= left:
            return self._idetify_elt
        
        func_value = self._idetify_elt
        leftpos = left + self._seg_length_half - 1 # leftmost segment
        rightpos = right + self._seg_length_half - 2 # rightmost segment

        while leftpos < rightpos-1:
            if leftpos&1 == 0:
                # if leftpos is right-child
                func_value = self._func(func_value, self._seg[leftpos])
            if rightpos&1 == 1:
                # if rightpos is leftchild
                func_value = self._func(func_value, self._seg[rightpos])
                rightpos -= 1
            # move up
            leftpos = leftpos//2
            rightpos = (rightpos-1)//2
        
        func_value = self._func(func_value, self._seg[leftpos])
        if leftpos != rightpos:
            func_value = self._func(func_value, self._seg[rightpos])
        return func_value

    def segsearch_right(self, condfunc, left=0):
        ''' Return min_i satisfying condfunc( func( A[left], ... , A[i])) 
        if impossible : return n
        '''
        # if impossible (ie. condfunc( func( A[left], ... , A[-1])) is False)
        if not condfunc(self._segquery(left, self._n)):
            return self._n
        
        # possible
        func_value = self._idetify_elt
        rightpos = left + self._seg_length_half - 1
        while True: 
            # while rightpos is the left-child, move bottom-up
            while rightpos&1 == 1:
                rightpos //= 2
            # try
            up_value_trial = self._func(func_value, self._seg[rightpos])
            if not condfunc(up_value_trial):
                # move up and right
                func_value = up_value_trial
                rightpos = (rightpos-1)//2 + 1
            else:
                # move top-down
                while rightpos < self._seg_length_half-1:
                    down_value_trial = self._func(func_value, self._seg[rightpos*2 + 1])
                    if condfunc(down_value_trial):
                        # move left-child
                        rightpos = rightpos*2 + 1
                    else:
                        # move right-child
                        func_value = down_value_trial
                        rightpos = rightpos*2 + 2
                return rightpos - self._seg_length_half + 1

import sys
input = sys.stdin.readline

n, m, k = map(int, input().split())
C = list(map(int, input().split()))
A = list(map(int, input().split()))

B = [k * A[i] for i in range(m)]
tree = SegmentTree(m, 10**18, min)
tree.setval(B)
ans = 10**18
for i in range(n):
    c = C[i] - 1
    b = tree.pointgetval(c)
    tree.pointupdate(c, b - A[c])
    ans = min(ans, tree.segquery(0, m))
    if i >= k - 1:
        c = C[i - k + 1] - 1
        b = tree.pointgetval(c)
        tree.pointupdate(c, b + A[c])
print(ans)
0