結果
問題 | No.489 株に挑戦 |
ユーザー |
![]() |
提出日時 | 2020-09-08 02:19:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 198 ms / 1,000 ms |
コード長 | 1,729 bytes |
コンパイル時間 | 202 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 82,556 KB |
最終ジャッジ日時 | 2024-07-20 00:29:55 |
合計ジャッジ時間 | 5,139 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
import sysimport io, osinput = sys.stdin.buffer.readline#input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readlinen, d, k = map(int, input().split())X = [(int(input()), i) for i in range(n)]class SegTree:def __init__(self, init_val, ide_ele, segfunc):self.n = len(init_val)self.num = 2**(self.n-1).bit_length()self.ide_ele = ide_eleself.segfunc = segfuncself.seg = [ide_ele]*2*self.num# set_valfor i in range(self.n):self.seg[i+self.num] = init_val[i]# builtfor i in range(self.num-1, 0, -1):self.seg[i] = self.segfunc(self.seg[2*i], self.seg[2*i+1])def update(self, k, x):k += self.numself.seg[k] = xwhile k:k = k >> 1self.seg[k] = self.segfunc(self.seg[2*k], self.seg[2*k+1])def query(self, l, r):if r <= l:return self.ide_elel += self.numr += self.numres = self.ide_elewhile l < r:if r & 1:r -= 1res = self.segfunc(res, self.seg[r])if l & 1:res = self.segfunc(res, self.seg[l])l += 1l = l >> 1r = r >> 1return resdef segfunc(x, y):if x[0] > y[0]:return xelif x[0] < y[0]:return yelse:if x[1] < y[1]:return xelse:return yseg = SegTree(X, (-1, -1), segfunc)M = 0for l in range(n):r = min(l+d, n-1)s, t = seg.query(l, r+1)temp = k*(s-X[l][0])if temp > M:M = tempans = (l, t)if M != 0:print(M)print(*ans)else:print(M)