結果
問題 | No.2549 Paint Eggs |
ユーザー | lloyz |
提出日時 | 2023-12-11 02:53:38 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 407 ms / 2,000 ms |
コード長 | 4,250 bytes |
コンパイル時間 | 198 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 118,456 KB |
最終ジャッジ日時 | 2023-12-11 02:53:56 |
合計ジャッジ時間 | 16,371 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 55 ms
66,292 KB |
testcase_01 | AC | 57 ms
68,320 KB |
testcase_02 | AC | 52 ms
66,296 KB |
testcase_03 | AC | 64 ms
72,648 KB |
testcase_04 | AC | 63 ms
70,672 KB |
testcase_05 | AC | 57 ms
68,324 KB |
testcase_06 | AC | 66 ms
72,652 KB |
testcase_07 | AC | 70 ms
74,176 KB |
testcase_08 | AC | 53 ms
65,872 KB |
testcase_09 | AC | 64 ms
72,648 KB |
testcase_10 | AC | 299 ms
108,352 KB |
testcase_11 | AC | 259 ms
118,456 KB |
testcase_12 | AC | 278 ms
102,492 KB |
testcase_13 | AC | 291 ms
104,396 KB |
testcase_14 | AC | 196 ms
101,920 KB |
testcase_15 | AC | 104 ms
76,936 KB |
testcase_16 | AC | 294 ms
103,540 KB |
testcase_17 | AC | 243 ms
102,376 KB |
testcase_18 | AC | 222 ms
101,472 KB |
testcase_19 | AC | 251 ms
100,180 KB |
testcase_20 | AC | 378 ms
114,772 KB |
testcase_21 | AC | 355 ms
114,672 KB |
testcase_22 | AC | 382 ms
114,772 KB |
testcase_23 | AC | 397 ms
114,552 KB |
testcase_24 | AC | 395 ms
114,772 KB |
testcase_25 | AC | 314 ms
114,792 KB |
testcase_26 | AC | 318 ms
114,572 KB |
testcase_27 | AC | 356 ms
114,768 KB |
testcase_28 | AC | 392 ms
114,452 KB |
testcase_29 | AC | 345 ms
114,548 KB |
testcase_30 | AC | 407 ms
114,772 KB |
testcase_31 | AC | 335 ms
114,776 KB |
testcase_32 | AC | 350 ms
114,804 KB |
testcase_33 | AC | 361 ms
115,028 KB |
testcase_34 | AC | 326 ms
114,576 KB |
testcase_35 | AC | 385 ms
114,796 KB |
testcase_36 | AC | 360 ms
114,780 KB |
testcase_37 | AC | 376 ms
114,768 KB |
testcase_38 | AC | 320 ms
114,936 KB |
testcase_39 | AC | 341 ms
114,772 KB |
testcase_40 | AC | 400 ms
114,636 KB |
testcase_41 | AC | 360 ms
114,424 KB |
testcase_42 | AC | 365 ms
114,292 KB |
testcase_43 | AC | 381 ms
114,292 KB |
testcase_44 | AC | 381 ms
114,416 KB |
ソースコード
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)