結果

問題 No.1095 Smallest Kadomatsu Subsequence
ユーザー convexineqconvexineq
提出日時 2020-06-26 22:36:58
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,068 ms / 2,000 ms
コード長 3,312 bytes
コンパイル時間 369 ms
コンパイル使用メモリ 87,236 KB
実行使用メモリ 147,828 KB
最終ジャッジ日時 2023-09-18 06:06:36
合計ジャッジ時間 13,641 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 76 ms
71,516 KB
testcase_01 AC 73 ms
71,372 KB
testcase_02 AC 73 ms
71,400 KB
testcase_03 AC 82 ms
75,688 KB
testcase_04 AC 82 ms
75,740 KB
testcase_05 AC 82 ms
75,908 KB
testcase_06 AC 83 ms
75,996 KB
testcase_07 AC 82 ms
75,900 KB
testcase_08 AC 82 ms
76,036 KB
testcase_09 AC 81 ms
75,876 KB
testcase_10 AC 83 ms
76,052 KB
testcase_11 AC 82 ms
76,076 KB
testcase_12 AC 80 ms
75,880 KB
testcase_13 AC 164 ms
80,968 KB
testcase_14 AC 173 ms
81,304 KB
testcase_15 AC 167 ms
80,896 KB
testcase_16 AC 169 ms
80,764 KB
testcase_17 AC 170 ms
81,028 KB
testcase_18 AC 178 ms
80,824 KB
testcase_19 AC 168 ms
81,176 KB
testcase_20 AC 168 ms
80,988 KB
testcase_21 AC 167 ms
80,896 KB
testcase_22 AC 167 ms
81,040 KB
testcase_23 AC 1,068 ms
145,248 KB
testcase_24 AC 980 ms
143,132 KB
testcase_25 AC 972 ms
144,252 KB
testcase_26 AC 959 ms
144,152 KB
testcase_27 AC 1,058 ms
143,896 KB
testcase_28 AC 647 ms
142,464 KB
testcase_29 AC 687 ms
142,276 KB
testcase_30 AC 830 ms
146,428 KB
testcase_31 AC 817 ms
144,440 KB
testcase_32 AC 826 ms
147,828 KB
権限があれば一括ダウンロードができます

ソースコード

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)
0