結果
問題 | No.489 株に挑戦 |
ユーザー |
|
提出日時 | 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 |
ソースコード
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 = nself._seg_length_half = 2**(n-1).bit_length()self._idetify_elt = idetify_eltself._seg = [idetify_elt]*(2*self._seg_length_half)self._func = funcdef setval(self, x_list):'''Set value : A = x_list'''assert (len(x_list) == self._n)# Set value at the bottomfor i in range(self._n):self._seg[i+self._seg_length_half-1] = x_list[i]# Build valuefor 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-thself._seg[pos] = x# Build bottom-upwhile pos:pos = (pos-1)//2self._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 < rightif right <= left:return self._idetify_eltfunc_value = self._idetify_eltleftpos = left + self._seg_length_half - 1 # leftmost segmentrightpos = right + self._seg_length_half - 2 # rightmost segmentwhile leftpos < rightpos-1:if leftpos&1 == 0:# if leftpos is right-childfunc_value = self._func(func_value, self._seg[leftpos])if rightpos&1 == 1:# if rightpos is leftchildfunc_value = self._func(func_value, self._seg[rightpos])rightpos -= 1# move upleftpos = leftpos//2rightpos = (rightpos-1)//2func_value = self._func(func_value, self._seg[leftpos])if leftpos != rightpos:func_value = self._func(func_value, self._seg[rightpos])return func_valuedef 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# possiblefunc_value = self._idetify_eltrightpos = left + self._seg_length_half - 1while True:# while rightpos is the left-child, move bottom-upwhile rightpos&1 == 1:rightpos //= 2# tryup_value_trial = self._func(func_value, self._seg[rightpos])if not condfunc(up_value_trial):# move up and rightfunc_value = up_value_trialrightpos = (rightpos-1)//2 + 1else:# move top-downwhile 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-childrightpos = rightpos*2 + 1else:# move right-childfunc_value = down_value_trialrightpos = rightpos*2 + 2return rightpos - self._seg_length_half + 1from collections import defaultdictfrom bisect import bisect_leftn, 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 = 0ANS = [0, 0]for i in range(n):max_ = SegTree.segquery(i, min(i + d + 1, n))res = (max_ - X[i]) * kif res > ans:ans = residx = bisect_left(Idxs[max_], i)ANS = [i, Idxs[max_][idx]]print(ans)if ans != 0:print(*ANS)