結果

問題 No.1687 What the Heck?
コンテスト
ユーザー lam6er
提出日時 2025-04-15 21:20:46
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,147 bytes
コンパイル時間 590 ms
コンパイル使用メモリ 81,800 KB
実行使用メモリ 110,032 KB
最終ジャッジ日時 2025-04-15 21:26:31
合計ジャッジ時間 7,195 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 1 WA * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

class MinSegmentTree:
    def __init__(self, size):
        self.n = size
        self.size = 1
        while self.size < self.n:
            self.size <<= 1
        self.tree = [float('inf')] * (2 * self.size)
        for i in range(self.n):
            self.tree[self.size + i] = i + 1
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = min(self.tree[2*i], self.tree[2*i+1])

    def update(self, pos, value):
        pos += self.size
        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_min(self, l, r):
        res = float('inf')
        l += self.size - 1
        r += self.size - 1
        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

class MaxSegmentTree:
    def __init__(self, size):
        self.n = size
        self.size = 1
        while self.size < self.n:
            self.size <<= 1
        self.tree = [float('-inf')] * (2 * self.size)
        for i in range(self.n):
            self.tree[self.size + i] = i + 1
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = max(self.tree[2*i], self.tree[2*i+1])

    def update(self, pos, value):
        pos += self.size
        self.tree[pos] = value
        pos >>= 1
        while pos >= 1:
            new_val = max(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_max(self, l, r):
        res = float('-inf')
        l += self.size - 1
        r += self.size - 1
        while l <= r:
            if l % 2 == 1:
                res = max(res, self.tree[l])
                l += 1
            if r % 2 == 0:
                res = max(res, self.tree[r])
                r -= 1
            l >>= 1
            r >>= 1
        return res

n = int(input())
P = list(map(int, input().split()))
rounds = [(i+1, P[i]) for i in range(n)]
rounds.sort(reverse=True, key=lambda x: x[0])

min_st = MinSegmentTree(n)
max_st = MaxSegmentTree(n)

total = 0

for current_i, p in rounds:
    if p + 1 <= n:
        min_card = min_st.query_min(p + 1, n)
    else:
        min_card = float('inf')
    if min_card != float('inf'):
        total += current_i
        min_st.update(min_card - 1, float('inf'))
        max_st.update(min_card - 1, float('-inf'))
    else:
        if p - 1 >= 1:
            max_card = max_st.query_max(1, p - 1)
        else:
            max_card = float('-inf')
        if max_card != float('-inf'):
            total -= current_i
            min_st.update(max_card - 1, float('inf'))
            max_st.update(max_card - 1, float('-inf'))
        else:
            min_st.update(p - 1, float('inf'))
            max_st.update(p - 1, float('-inf'))

print(total)
0