結果

問題 No.1095 Smallest Kadomatsu Subsequence
ユーザー lam6er
提出日時 2025-03-20 18:55:58
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 806 ms / 2,000 ms
コード長 3,759 bytes
コンパイル時間 366 ms
コンパイル使用メモリ 82,288 KB
実行使用メモリ 170,332 KB
最終ジャッジ日時 2025-03-20 18:57:30
合計ジャッジ時間 11,255 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import bisect
inf = float('inf')

class SegmentTree:
    def __init__(self, max_size):
        self.N = 1
        while self.N < max_size:
            self.N <<= 1
        self.size = self.N
        self.tree = [inf] * (2 * self.N)
    
    def update_point(self, pos, value):
        pos += self.N
        if self.tree[pos] > value:
            self.tree[pos] = value
            pos >>= 1
            while pos >= 1:
                new_val = min(self.tree[2*pos], self.tree[2*pos+1])
                if self.tree[pos] == new_val:
                    break
                self.tree[pos] = new_val
                pos >>= 1
    
    def query_range(self, l, r):
        res = inf
        l += self.N
        r += self.N
        while l <= r:
            if l % 2 == 1:
                res = min(res, self.tree[l])
                l += 1
            if r % 2 == 0:
                res = min(res, self.tree[r])
                r -= 1
            l >>= 1
            r >>= 1
        return res

def main():
    input = sys.stdin.read().split()
    N = int(input[0])
    A = list(map(int, input[1:N+1]))
    
    sorted_A = sorted(A)
    rank = {v:i for i, v in enumerate(sorted_A)}
    r = [rank[a] for a in A]
    max_rank = len(sorted_A) - 1
    
    # Compute min_left_less and min_left_greater
    left_st = SegmentTree(max_rank + 1)
    min_left_less = [inf] * N
    min_left_greater = [inf] * N
    for j in range(N):
        current_r = r[j]
        # Query for min_left_less
        if current_r > 0:
            q_l = 0
            q_r = current_r - 1
            min_val = left_st.query_range(q_l, q_r)
        else:
            min_val = inf
        min_left_less[j] = min_val
        # Query for min_left_greater
        if current_r + 1 <= max_rank:
            q_l = current_r + 1
            q_r = max_rank
            min_val = left_st.query_range(q_l, q_r)
        else:
            min_val = inf
        min_left_greater[j] = min_val
        # Update left_st
        left_st.update_point(current_r, A[j])
    
    # Compute min_right_less and min_right_greater
    right_st = SegmentTree(max_rank + 1)
    min_right_less = [inf] * N
    min_right_greater = [inf] * N
    for j in range(N-1, -1, -1):
        current_r = r[j]
        # Query for min_right_less
        if current_r > 0:
            q_l = 0
            q_r = current_r - 1
            min_val = right_st.query_range(q_l, q_r)
        else:
            min_val = inf
        min_right_less[j] = min_val
        # Query for min_right_greater
        if current_r + 1 <= max_rank:
            q_l = current_r + 1
            q_r = max_rank
            min_val = right_st.query_range(q_l, q_r)
        else:
            min_val = inf
        min_right_greater[j] = min_val
        # Update right_st
        right_st.update_point(current_r, A[j])
    
    ans = inf
    # Check each possible middle element j (i < j < k)
    for j in range(1, N-1):  # j ranges from 1 to N-2 inclusive
        # Case 1: j is the max, so we need elements < A[j] on both sides
        case1_sum = inf
        left_less = min_left_less[j]
        right_less = min_right_less[j]
        if left_less != inf and right_less != inf:
            case1_sum = left_less + A[j] + right_less
        
        # Case 2: j is the min, so we need elements > A[j] on both sides
        case2_sum = inf
        left_greater = min_left_greater[j]
        right_greater = min_right_greater[j]
        if left_greater != inf and right_greater != inf:
            case2_sum = left_greater + A[j] + right_greater
        
        current_min = min(case1_sum, case2_sum)
        if current_min < ans:
            ans = current_min
    
    print(ans if ans != inf else -1)

if __name__ == '__main__':
    main()
0