結果
問題 | No.1095 Smallest Kadomatsu Subsequence |
ユーザー |
![]() |
提出日時 | 2020-06-26 22:01:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,635 ms / 2,000 ms |
コード長 | 3,583 bytes |
コンパイル時間 | 182 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 263,576 KB |
最終ジャッジ日時 | 2024-07-04 21:10:34 |
合計ジャッジ時間 | 17,111 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
from bisect import bisect_right, bisect_left# instead of AVLTreeclass BITbisect():def __init__(self, InputProbNumbers):# 座圧self.ind_to_co = [-10**18]self.co_to_ind = {}for ind, num in enumerate(sorted(list(set(InputProbNumbers)))):self.ind_to_co.append(num)self.co_to_ind[num] = ind+1self.max = len(self.co_to_ind)self.data = [0]*(self.max+1)def __str__(self):retList = []for i in range(1, self.max+1):x = self.ind_to_co[i]if self.count(x):c = self.count(x)for _ in range(c):retList.append(x)return "[" + ", ".join([str(a) for a in retList]) + "]"def __getitem__(self, key):key += 1s = 0ind = 0l = self.max.bit_length()for i in reversed(range(l)):if ind + (1<<i) <= self.max:if s + self.data[ind+(1<<i)] < key:s += self.data[ind+(1<<i)]ind += (1<<i)if ind == self.max or key < 0:raise IndexError("BIT index out of range")return self.ind_to_co[ind+1]def __len__(self):return self._query_sum(self.max)def __contains__(self, num):if not num in self.co_to_ind:return Falsereturn self.count(num) > 0# 0からiまでの区間和# 左に進んでいくdef _query_sum(self, i):s = 0while i > 0:s += self.data[i]i -= i & -ireturn s# i番目の要素にxを足す# 上に登っていくdef _add(self, i, x):while i <= self.max:self.data[i] += xi += i & -i# 値xを挿入def push(self, x):if not x in self.co_to_ind:raise KeyError("The pushing number didnt initialized")self._add(self.co_to_ind[x], 1)# 値xを削除def delete(self, x):if not x in self.co_to_ind:raise KeyError("The deleting number didnt initialized")if self.count(x) <= 0:raise ValueError("The deleting number doesnt exist")self._add(self.co_to_ind[x], -1)# 要素xの個数def count(self, x):return self._query_sum(self.co_to_ind[x]) - self._query_sum(self.co_to_ind[x]-1)# 値xを超える最低inddef bisect_right(self, x):if x in self.co_to_ind:i = self.co_to_ind[x]else:i = bisect_right(self.ind_to_co, x) - 1return self._query_sum(i)# 値xを下回る最低inddef bisect_left(self, x):if x in self.co_to_ind:i = self.co_to_ind[x]else:i = bisect_left(self.ind_to_co, x)if i == 1:return 0return self._query_sum(i-1)import sysinput = sys.stdin.readlineINF = 10**18N = int(input())A = list(map(int, input().split()))Bit1 = BITbisect(A)Bit2 = BITbisect(A)ans = INFfor a in A:Bit2.push(a)for i, a in enumerate(A):Bit2.delete(a)if i == 0 or i == N-1:Bit1.push(a)continuec1 = Bit1[0]c2 = Bit2[0]if a > c1 and a > c2:ans = min(ans, a+c1+c2)ind1 = Bit1.bisect_left(a)ind2 = Bit2.bisect_left(a)if ind1 < len(Bit1) and ind2 < len(Bit2):b1 = Bit1[ind1]b2 = Bit2[ind2]ans = min(ans, a + b1 + b2)Bit1.push(a)if ans == INF:print(-1)else:print(ans)