結果

問題 No.1095 Smallest Kadomatsu Subsequence
ユーザー convexineq
提出日時 2020-06-26 22:36:58
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 981 ms / 2,000 ms
コード長 3,312 bytes
コンパイル時間 312 ms
コンパイル使用メモリ 82,332 KB
実行使用メモリ 144,384 KB
最終ジャッジ日時 2024-07-04 22:23:11
合計ジャッジ時間 11,264 ms
ジャッジサーバーID
(参考情報)
judge3 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

"""
C++ std::map
n: 0
self.dic dict
"""
class BIT: #0-indexed
def __init__(self, n):
self.size = n
self.tree = [0]*(n+1)
self.depth = n.bit_length()
self.n0 = 1<<self.depth
# self.element = [0]*(n+1)
def get_sum(self, i): #a_0 + ... + a_{i} #
s = 0; i += 1
while i > 0:
s += self.tree[i]
i -= i & -i
return s
def query(self,l,r): #a_l + ... + a_r
return self.get_sum(r) - self.get_sum(l-1)
def add(self, i, x):
i += 1
while i <= self.size:
self.tree[i] += x
i += i & -i
# self.element[i] += x
#def get(self,i): return element[i]
def bisect_left(self,w):
# w index
#w self.size
if w <= 0: return 0
x,k = 0,self.n0
for _ in range(self.depth):
k >>= 1
if x+k <= self.size and self.tree[x+k] < w:
w -= self.tree[x+k]
x += k
return x
class stdmap:
def __init__(self, n):
self.size = n+1
self.keys = set()
self.B = BIT(n+1) # 1 0
self.dic = [0]*(n+1) #
def __contains__(self, k):
return k in self.keys
def insert(self,a,b): # a b
if a not in self.keys:
self.B.add(a,1)
self.keys.add(a)
self.dic[a] = b
def remove(self,a): # a
self.keys.remove(a)
self.B.add(a,-1)
def lower_bound(self,k): # k key
return self.B.bisect_left(self.B.get_sum(k-1)+1)
def kth_key(self,k): # k key
return self.B.bisect_left(k)
def kth_value(self,k): # k map
return self.dic[self.B.bisect_left(k)]
def prev_key(self,k): #key
idx = self.B.get_sum(k)
assert idx != 0
return self.B.bisect_left(idx-1)
def next_key(self,k):
idx = self.B.get_sum(k)
assert idx != self.size
return self.B.bisect_left(idx+1)
def __getitem__(self,item):
return self.dic[item]
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline
n,*a = map(int,read().split())
sa = sorted(a+[0]+[1<<29])
zaatu = {ai:i for i,ai in enumerate(sa)}
b1 = stdmap(n+2)
b2 = stdmap(n+2)
for i in range(n+2):
b2.insert(i,1)
b1.insert(0,1)
b1.insert(n+1,1)
ans = INF = 1<<31
n += 1
for i,ai in enumerate(a):
z = zaatu[ai]
b2.remove(z)
i1 = b1.lower_bound(z)
i2 = b2.lower_bound(z)
if i1 < n and i2 < n:
r = sa[i1] + ai + sa[i2]
#print(r,z,i1,i2,ai)
ans = min(ans,r)
i1 = b1.kth_key(2)
i2 = b2.kth_key(2)
if i1 < z and i2 < z:
r = sa[i1] + ai + sa[i2]
#print(b2.keys)
#print(r,z,i1,i2,ai)
ans = min(ans,r)
b1.insert(z,1)
if ans==INF: print(-1)
else: print(ans)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0