結果

問題 No.489 株に挑戦
ユーザー lloyz
提出日時 2023-01-23 00:04:23
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 225 ms / 1,000 ms
コード長 4,262 bytes
コンパイル時間 198 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 102,320 KB
最終ジャッジ日時 2024-06-25 01:28:08
合計ジャッジ時間 6,498 ms
ジャッジサーバーID
(参考情報)
judge5 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

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
from collections import defaultdict
from bisect import bisect_left
n, d, k = map(int, input().split())
X = [int(input()) for _ in range(n)]
Idxs = defaultdict(list)
for i in range(n):
Idxs[X[i]].append(i)
SegTree = SegmentTree(n)
SegTree.setval(X)
ans = 0
ANS = [0, 0]
for i in range(n):
max_ = SegTree.segquery(i, min(i + d + 1, n))
res = (max_ - X[i]) * k
if res > ans:
ans = res
idx = bisect_left(Idxs[max_], i)
ANS = [i, Idxs[max_][idx]]
print(ans)
if ans != 0:
print(*ANS)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0