結果
問題 | No.1095 Smallest Kadomatsu Subsequence |
ユーザー |
![]() |
提出日時 | 2021-05-28 20:00:08 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 991 ms / 2,000 ms |
コード長 | 1,868 bytes |
コンパイル時間 | 206 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 126,116 KB |
最終ジャッジ日時 | 2024-11-07 07:48:09 |
合計ジャッジ時間 | 12,002 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
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.numlres = self.ide_elerres = self.ide_elewhile l < r:if r & 1:r -= 1rres = self.segfunc(self.seg[r], rres)if l & 1:lres = self.segfunc(lres, self.seg[l])l += 1l = l >> 1r = r >> 1res = self.segfunc(lres, rres)return resdef __str__(self): # for debugarr = [self.query(i,i+1) for i in range(self.n)]return str(arr)n = int(input())A = list(map(int, input().split()))B = []for i, a in enumerate(A):B.append((i, a))B.sort(key=lambda x: -x[1])INF = 10**18ans = INFseg = SegTree([INF]*n, INF, min)for i, a in B:l = seg.query(0, i)r = seg.query(i+1, seg.n)if l != INF and r != INF:ans = min(ans, l+a+r)seg.update(i, a)seg = SegTree([INF]*n, INF, min)for i, a in reversed(B):l = seg.query(0, i)r = seg.query(i+1, seg.n)if l != INF and r != INF:ans = min(ans, l+a+r)seg.update(i, a)if ans != INF:print(ans)else:print(-1)