結果

問題 No.1687 What the Heck?
コンテスト
ユーザー lam6er
提出日時 2025-04-15 21:08:13
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,540 bytes
コンパイル時間 254 ms
コンパイル使用メモリ 82,384 KB
実行使用メモリ 134,784 KB
最終ジャッジ日時 2025-04-15 21:13:57
合計ジャッジ時間 5,535 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 8 WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

class SegmentTree:
    def __init__(self, size):
        self.n = 1
        while self.n < size:
            self.n <<= 1
        self.min_tree = [float('inf')] * (2 * self.n)
        self.max_tree = [-float('inf')] * (2 * self.n)
        for i in range(size):
            self.min_tree[self.n + i] = i + 1
            self.max_tree[self.n + i] = i + 1
        for i in range(self.n - 1, 0, -1):
            self.min_tree[i] = min(self.min_tree[2*i], self.min_tree[2*i+1])
            self.max_tree[i] = max(self.max_tree[2*i], self.max_tree[2*i+1])
    
    def delete(self, pos):
        idx = pos - 1 + self.n
        self.min_tree[idx] = float('inf')
        self.max_tree[idx] = -float('inf')
        idx >>= 1
        while idx >= 1:
            new_min = min(self.min_tree[2*idx], self.min_tree[2*idx+1])
            new_max = max(self.max_tree[2*idx], self.max_tree[2*idx+1])
            if self.min_tree[idx] == new_min and self.max_tree[idx] == new_max:
                break
            self.min_tree[idx] = new_min
            self.max_tree[idx] = new_max
            idx >>= 1
    
    def query_min(self, l, r):
        res = float('inf')
        l += self.n - 1
        r += self.n - 1
        while l <= r:
            if l % 2 == 1:
                res = min(res, self.min_tree[l])
                l += 1
            if r % 2 == 0:
                res = min(res, self.min_tree[r])
                r -= 1
            l >>= 1
            r >>= 1
        return res
    
    def query_max(self, l, r):
        res = -float('inf')
        l += self.n - 1
        r += self.n - 1
        while l <= r:
            if l % 2 == 1:
                res = max(res, self.max_tree[l])
                l += 1
            if r % 2 == 0:
                res = max(res, self.max_tree[r])
                r -= 1
            l >>= 1
            r >>= 1
        return res

def main():
    input = sys.stdin.read().split()
    N = int(input[0])
    P = list(map(int, input[1:N+1]))
    rounds = [(i+1, p) for i, p in enumerate(P)]
    rounds.sort(reverse=True, key=lambda x: x[0])
    
    st = SegmentTree(N)
    ans = 0
    
    for i, p in rounds:
        min_val = st.query_min(p + 1, N)
        if min_val != float('inf'):
            ans += i
            st.delete(min_val)
        else:
            max_val = st.query_max(1, p)
            if max_val == p:
                st.delete(max_val)
            else:
                ans -= i
                st.delete(max_val)
    print(ans)

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