結果

問題 No.1438 Broken Drawers
ユーザー lam6er
提出日時 2025-04-09 21:00:50
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 456 ms / 2,000 ms
コード長 1,661 bytes
コンパイル時間 321 ms
コンパイル使用メモリ 82,884 KB
実行使用メモリ 114,344 KB
最終ジャッジ日時 2025-04-09 21:01:17
合計ジャッジ時間 9,268 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

class SegmentTree:
    def __init__(self, size):
        self.n = 1
        while self.n < size:
            self.n <<= 1
        self.tree = [0] * (2 * self.n)
    
    def update(self, a_val, value):
        idx = a_val - 1 + self.n  # Convert 1-based a_val to 0-based index in the leaf nodes
        if self.tree[idx] >= value:
            return
        self.tree[idx] = value
        idx >>= 1
        while idx >= 1:
            new_val = max(self.tree[2*idx], self.tree[2*idx+1])
            if self.tree[idx] == new_val:
                break
            self.tree[idx] = new_val
            idx >>= 1
    
    def query(self, l, r):
        res = 0
        l += self.n
        r += self.n
        while l < r:
            if l % 2 == 1:
                res = max(res, self.tree[l])
                l += 1
            if r % 2 == 1:
                r -= 1
                res = max(res, self.tree[r])
            l >>= 1
            r >>= 1
        return res

N = int(input())
A = list(map(int, input().split()))
drawers = [(i + 1, a) for i, a in enumerate(A)]  # (drawer number, A value)
drawers.sort(key=lambda x: x[1])

st = SegmentTree(N)
used = [False] * (N + 2)  # 1-based for drawer numbers

max_len = 0

for k, a in drawers:
    blocked = False
    if k + 1 <= N:
        a_k_plus_1 = A[k]  # A[k] is the value of the (k+1)th drawer (0-based index)
        if a_k_plus_1 < a:
            if used[k+1]:
                blocked = True
    if not blocked:
        current_max = st.query(0, a - 1)
        dp_k = current_max + 1
        if dp_k > max_len:
            max_len = dp_k
        st.update(a, dp_k)
        used[k] = True

print(max_len)
0