結果
問題 |
No.1095 Smallest Kadomatsu Subsequence
|
ユーザー |
![]() |
提出日時 | 2020-06-27 14:27:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,214 ms / 2,000 ms |
コード長 | 1,658 bytes |
コンパイル時間 | 173 ms |
コンパイル使用メモリ | 82,068 KB |
実行使用メモリ | 108,952 KB |
最終ジャッジ日時 | 2024-07-05 09:08:35 |
合計ジャッジ時間 | 13,001 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
class SegmentTree(): def __init__(self, arr, func=min, ie=2**63): self.h = (len(arr) - 1).bit_length() self.n = 2**self.h self.ie = ie self.func = func self.tree = [ie for _ in range(2 * self.n)] for i in range(len(arr)): self.tree[self.n + i] = arr[i] for i in range(1, self.n)[::-1]: self.tree[i] = func(self.tree[2 * i], self.tree[2 * i + 1]) def set(self, idx, x): idx += self.n self.tree[idx] = x while idx: idx >>= 1 self.tree[idx] = self.func(self.tree[2 * idx], self.tree[2 * idx + 1]) def query(self, lt, rt): lt += self.n rt += self.n vl = vr = self.ie while rt - lt > 0: if lt & 1: vl = self.func(vl, self.tree[lt]) lt += 1 if rt & 1: rt -= 1 vr = self.func(self.tree[rt], vr) lt >>= 1 rt >>= 1 return self.func(vl, vr) INF = 10**18 N = int(input()) A = list(map(int, input().split())) S = sorted([(A[i], i) for i in range(N)]) res = INF st1 = SegmentTree([INF] * N, min, INF) for i in range(N): a, idx = S[i] st1.set(idx, a) lt = st1.query(0, idx) rt = st1.query(idx + 1, N) if lt == INF or rt == INF: continue res = min(res, lt + rt + a) st2 = SegmentTree([INF] * N, min, INF) for i in range(N)[::-1]: a, idx = S[i] st2.set(idx, a) lt = st2.query(0, idx) rt = st2.query(idx + 1, N) if lt == INF or rt == INF: continue res = min(res, lt + rt + a) print(res if res != INF else -1)