#622261 (PyPy3) No.1095 Smallest Kadomatsu Subsequence

• 問題: No.1095 Smallest Kadomatsu Subsequence
• ユーザー: None
• 提出日時: 2021-02-25 19:00:03
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 1,215 ms / 2,000 ms
• コード長: 12,889 bytes
• コンパイル時間: 155 ms
• コンパイル使用メモリ: 82,304 KB
• 実行使用メモリ: 205,136 KB
• 最終ジャッジ日時: 2024-10-01 09:11:24
• 合計ジャッジ時間: 15,076 ms
• ジャッジサーバーID （参考情報）: judge4 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	39 ms; 55,296 KB
testcase_01	AC	40 ms; 54,908 KB
testcase_02	AC	39 ms; 55,424 KB
testcase_03	AC	51 ms; 64,384 KB
testcase_04	AC	49 ms; 63,360 KB
testcase_05	AC	50 ms; 62,720 KB
testcase_06	AC	50 ms; 63,488 KB
testcase_07	AC	51 ms; 63,104 KB
testcase_08	AC	49 ms; 63,360 KB
testcase_09	AC	50 ms; 62,976 KB
testcase_10	AC	49 ms; 63,488 KB
testcase_11	AC	49 ms; 63,616 KB
testcase_12	AC	49 ms; 63,744 KB
testcase_13	AC	158 ms; 81,016 KB
testcase_14	AC	160 ms; 80,948 KB
testcase_15	AC	161 ms; 80,688 KB
testcase_16	AC	161 ms; 81,400 KB
testcase_17	AC	160 ms; 81,400 KB
testcase_18	AC	169 ms; 81,024 KB
testcase_19	AC	165 ms; 81,028 KB
testcase_20	AC	159 ms; 81,396 KB
testcase_21	AC	161 ms; 80,852 KB
testcase_22	AC	164 ms; 81,032 KB
testcase_23	AC	1,215 ms; 203,156 KB
testcase_24	AC	1,065 ms; 201,108 KB
testcase_25	AC	1,202 ms; 204,984 KB
testcase_26	AC	1,196 ms; 205,136 KB
testcase_27	AC	1,098 ms; 201,552 KB
testcase_28	AC	1,128 ms; 197,256 KB
testcase_29	AC	1,122 ms; 197,612 KB
testcase_30	AC	1,110 ms; 197,364 KB
testcase_31	AC	1,075 ms; 196,528 KB
testcase_32	AC	1,096 ms; 197,124 KB

ソースコード

class Bit:
    def __init__(self, n, array=[]):
        """
        :param n: number of elements
        """
        self.n = n
        self.tree = [0]*(n+1)
        self.depth = n.bit_length() - 1
        for i, a in enumerate(array):
            self.add(i, a)

    def get(self,i):
        """ return summation of elements in [0,i) """
        s = 0
        i -= 1
        while i >= 0:
            s += self.tree[i]
            i = (i & (i + 1) )- 1
        return s

    def build(self, array):
        """ bulid BIT from array """
        for i, a in enumerate(array):
            self.add(i, a)

    def add(self, i, x):
        """ add x to i-th element """
        while i < self.n:
            self.tree[i] += x
            i |= i + 1

    def get_range(self,i,j):
        """ return summation of elements in [i,j) """
        if i == 0:
            return self.get(j)
        return self.get(j)-self.get(i)

    def lower_bound(self, x, equal=False):
        """
        return tuple = (return maximum i s.t. a0+a1+...+ai < x (if not existing, -1 ) , a0+a1+...+ai )
        if one wants to include equal (i.e., a0+a1+...+ai <= x), please set equal = True
        (Cation) We must assume that A_i>=0
        """
        sum_ = 0
        pos = -1    # 1-indexed の時は pos = 0
        if not equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] < x:  # 1-indexed の時は k <= self.n
                    sum_ += self.tree[k]
                    pos += 1 << i
        if equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] <= x: # 1-indexed の時は k <= self.n
                    sum_ += self.tree[k]
                    pos += 1 << i
        return pos, sum_

    def __getitem__(self, i):
        """ [a0, a1, a2, ...] """
        if i<0: i=self.n+i
        return self.get_range(i,i+1)

    def __iter__(self):
        """ [a0, a1, a2, ...] """
        for i in range(self.n):
            yield self.get_range(i,i+1)

    def __str__(self):
        text1 = " ".join(["element:            "] + list(map(str, self)))
        text2 = " ".join(["cumsum(1-indexed):  "]+list(str(self.get(i)) for i in range(1,self.n+1)))
        return "\n".join((text1, text2))

class BitImos:
    def __init__(self, n, array=[]):
        self.n = n
        self.p = Bit(self.n + 1)
        self.q = Bit(self.n + 1)
        for i, a in enumerate(array):
            self.add(i, a)


    def add(self, s, x):
        self.add_range(s,s+1,x)

    def add_range(self, s, t, x):
        """ add x to a close-interval [s,t)"""
        self.p.add(s, -x * s)
        self.p.add(t, x * t)
        self.q.add(s, x)
        self.q.add(t, -x)

    def build(self, array):
        """ bulid BIT from array """
        for i, a in enumerate(array):
            self.add(i, a)

    def get(self,s):
        return self.get_range(s,s+1)

    def get_range(self,s,t):
        """ return summation of elements in [s,t) """
        return self.p.get(t)+self.q.get(t)*t-self.p.get(s)-self.q.get(s)*s

    def __getitem__(self, s):
        """ return s-th element of array (not sum-array) """
        return self.q.get(s+1)

    def __iter__(self):
        """ max(self) returns what we obtain by the Imos method"""
        for t in range(self.n):
            yield self.q.get(t+1)

    def __str__(self):
        text1 = " ".join(["element: "] + list(map(str, self)))
        return text1

class SortedList:
    def __init__(self, n, A=[]):
        """
        :param n: miximum value of A
        self.size: number of elements in BitSet
        """
        self.n = n
        self.p = Bit(self.n + 1)
        self.size = 0
        self.flip = 0
        for a in A:
            self.add(a)

    def add(self,x):
        self.p.add(x, 1)
        self.size += 1
        self.flip += self.size - self.p.get(x+1)         # we can remove this if we do not use flip_number

    def remove(self,x):
        self.p.add(x, -1)
        self.size -= 1

    def bisect_left(self,x):
        """ return bisect_left(sorted(B),x) """
        if x <= self.n:
            return self.p.get(x)
        else:
            return self.size

    def bisect_right(self,x):
        """ return bisect_right(sorted(B),x) """
        x += 1
        if x <= self.n:
            return self.p.get(x)
        else:
            return self.size

    def flip_counter(self):
        return self.flip

    def count(self,x):
        return self.p[x]

    def count_range(self,l,r):
        """ return number of elements in closed set [l,r]"""
        return self.bisect_right(r)-self.bisect_left(l)

    def minimum(self,k=1):
        """ return k-th minimum value """
        if k <= self.size:
            return self.p.lower_bound(k)[0] + 1
        else:
            sys.stderr.write("minimum: list index out of range (k={0})\n".format(k))

    def min(self):
        return self.minimum(1)

    def max(self):
        return self.p.lower_bound(self.size)[0] + 1

    def upper_bound(self,x,equal=False):
        """ return maximum element lower than x """
        k = self.p.get(x+equal)
        if k:
            return self.minimum(k)
        else:
            sys.stderr.write("upper_bound: no element smaller than {0} in this BitSet\n".format(x))

    def lower_bound(self,x,equal=False):
        """ return minimum element greater than x """
        k =self.p.get(x+1-equal)+1
        if k <= self.size:
            return self.minimum(k)
        else:
            sys.stderr.write("lower_bound: no element larger than {0} in this BitSet\n".format(x))

    def __getitem__(self, k):
        """
        return k-th minimum element (0-indexed)
        B[k] = sorted(A)[k]
        """
        if len(self)==0:
            sys.stderr.write("__getitem__: no elements exist in this BitSet\n")
        elif k >= len(self):
            sys.stderr.write("__getitem__: index (={0}) is larger than the maximum index (={1})\n".format(k,len(self)-1))
        elif k >= 0:
            return self.minimum(k+1)
        else:
            sys.stderr.write("__getitem__: index (={0}) is negative \n".format(k))

    def __len__(self):
        return self.size

    def __iter__(self):
        """ return sorted list """
        for i in range(self.n+1):
            if self.p[i]:
                for _ in range(self.p[i]):
                    yield i

    def __str__(self):
        """ return sorted list """
        text1 = " ".join(list(map(str, self)))
        return "[" + text1 + "]"

class SortedList2:
    """ if we need compress """
    def __init__(self, data, A=[]):
        """
        self.size: number of elements in BitSet
        """
        self.data = sorted(list(set(data)))
        self.n = len(self.data)
        self.p = Bit(self.n + 1)
        self.size = 0
        self.flip = 0
        self.code = {}
        self.decode = []
        for i, b in enumerate(self.data):
            self.code[b] = i
            self.decode.append(b)
        for a in A:
            self.add(a)

    def add(self,x):
        self.p.add(self.code[x], 1)
        self.size += 1
        self.flip += self.size - self.p.get(self.code[x]+1)        # we can remove this if we do not use flip_number

    def remove(self,x):
        self.p.add(self.code[x], -1)
        self.size -= 1

    def bisect_left(self,x):
        """ return bisect_left(sorted(B),x) """
        if x in self.code.keys():
            return self.p.get(self.code[x])
        else:
            return self.p.get(bisect_right(self.data,x))

    def bisect_right(self,x):
        """ return bisect_right(sorted(B),x) """
        x += 1
        if x in self.code.keys():
            return self.p.get(self.code[x])
        else:
            return self.p.get(bisect_right(self.data,x))

    def count(self,x):
        return self.p[self.code[x]]

    def count_range(self,l,r):
        """ return number of elements in closed set [l,r]"""
        return self.bisect_right(r)-self.bisect_left(l)

    def minimum(self,k=1):
        """ return k-th minimum value """
        if k <= self.size:
            return self.decode[self.p.lower_bound(k)[0] + 1]
        else:
            sys.stderr.write("minimum: list index out of range (k={0})\n".format(k))

    def min(self):
        return self.minimum(1)

    def max(self):
        return self.decode[self.p.lower_bound(self.size)[0] + 1]

    def upper_bound(self,x,equal=False):
        """ return maximum element lower than x """
        if x in self.code.keys():
            y = self.code[x] + equal
        else:
            y = bisect_right(self.data, x)
        k = self.p.get(y)
        if k:
            return self.minimum(k)
        else:
            sys.stderr.write("upper_bound: no element smaller than {0} in this BitSet\n".format(x))

    def lower_bound(self,x,equal=False):
        """ return minimum element greater than x """
        if x in self.code.keys():
            y = self.code[x] + 1 - equal
        else:
            y = bisect_left(self.data, x)
        k =self.p.get(y)+1
        if k <= self.size:
            return self.minimum(k)
        else:
            sys.stderr.write("lower_bound: no element larger than {0} in this BitSet\n".format(x))

    def nearest(self,x,k):
        """ return k-th nearest value to x """
        if k>len(self):
            sys.stderr.write("nearest: k (= {0}) is larger than the size of this BitSet\n".format(k))
            return

        def test(d):
            r=self.bisect_right(x+d)-1
            l=self.bisect_left(x-d)
            return r-l+1<=k

        ok,ng=0,10**18+1
        while abs(ok-ng)>1:
            mid=(ok+ng)//2
            if test(mid):
                ok=mid
            else:
                ng=mid
        d=ok

        r=self.bisect_right(x+d)-1
        l=self.bisect_left(x-d)
        if d==0:
            R=self.lower_bound(x,equal=True)
            L=self.upper_bound(x,equal=True)
            if abs(x-L)==abs(R-x):
                if self.count(L)>=k: return L
                else: return R
            elif abs(x-L)<abs(R-x): return L
            else: return R
        elif r-l+1==k:
            R=self[r]
            L=self[l]
            if abs(x-L)<=abs(R-x): return R
            else: return L
        else:
            if l<=0: return self[r+1]
            elif r>=len(self)-1: return self[l-1]
            else:
                R=self[r+1]
                L=self[l-1]
                if abs(x-L)==abs(R-x):
                    if self.count(L)>=k-(r-l+1):
                        return L
                    else: return R
                elif abs(x-L)<abs(R-x): return L
                else: return R

    def __getitem__(self, k):
        """
        return k-th minimum element (0-indexed)
        B[k] = sorted(A)[k]
        """
        if len(self)==0:
            sys.stderr.write("__getitem__: no elements exist in this BitSet\n")
        elif k >= len(self):
            sys.stderr.write("__getitem__: index (={0}) is larger than the maximum index (={1})\n".format(k,len(self)-1))
        elif k >= 0:
            return self.minimum(k+1)
        else:
            sys.stderr.write("__getitem__: index (={0}) is negative \n".format(k))

    def __len__(self):
        return self.size

    def __iter__(self):
        """ return sorted list """
        for i in range(self.n+1):
            if self.p[i]:
                for _ in range(self.p[i]):
                    yield self.decode[i]

    def __str__(self):
        """ return sorted list """
        text1 = " ".join(list(map(str, self)))
        return "[" + text1 + "]"

###################################################
def example():
    global input
    example = iter(
        """
6
10 5 1 5 10 7
        """
            .strip().split("\n"))
    input = lambda: next(example)
###################################################

import sys
input = sys.stdin.readline
from bisect import bisect_left, bisect_right

# example()

N=int(input())
A=list(map(int, input().split()))

left = SortedList2(A)
left.add(A[0])

left_u=[None]*N
left_d=[None]*N

for i in range(1,N):
    u=left.lower_bound(A[i],equal=False)
    d=left.min()
    if u!=None:
        left_u[i]=u
    if d<A[i]:
        left_d[i]=d
    left.add(A[i])

right = SortedList2(A)
right.add(A[-1])

right_u=[None]*N
right_d=[None]*N

for i in range(N-1)[::-1]:
    u=right.lower_bound(A[i],equal=False)
    d=right.min()
    if u!=None:
        right_u[i]=u
    if d<A[i]:
        right_d[i]=d
    right.add(A[i])

res=float("inf")
for i in range(1,N-1):
    if left_u[i] is not None and right_u[i] is not None:
        res=min(A[i]+left_u[i]+right_u[i],res)
    if left_d[i] is not None and right_d[i] is not None:
        res=min(A[i]+left_d[i]+right_d[i],res)

print(res if res!=float("inf") else -1)