結果

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

ソースコード

diff # 

class SegmentTreeNode:
    def __init__(self, l, r):
        self.l = l
        self.r = r
        self.left = None
        self.right = None
        self.min_val = l
        self.max_val = r
        self.count = 1 if l == r else 0

    def delete(self, x):
        if self.l == self.r:
            self.count = 0
            self.min_val = None
            self.max_val = None
            return
        if x <= self.left.r:
            self.left.delete(x)
        else:
            self.right.delete(x)
        self.min_val = None
        if self.left.min_val is not None:
            self.min_val = self.left.min_val
        if self.right.min_val is not None:
            if self.min_val is None or self.right.min_val < self.min_val:
                self.min_val = self.right.min_val
        self.max_val = None
        if self.left.max_val is not None:
            self.max_val = self.left.max_val
        if self.right.max_val is not None:
            if self.max_val is None or self.right.max_val > self.max_val:
                self.max_val = self.right.max_val
        self.count = self.left.count + self.right.count

    def find_smallest_greater_than(self, x):
        if self.count == 0:
            return None
        if self.max_val <= x:
            return None
        if self.l == self.r:
            return self.l
        left_res = self.left.find_smallest_greater_than(x)
        if left_res is not None:
            return left_res
        return self.right.find_smallest_greater_than(x)

    def find_largest_less_or_equal(self, x):
        if self.count == 0:
            return None
        if self.min_val > x:
            return None
        if self.l == self.r:
            return self.l
        right_res = self.right.find_largest_less_or_equal(x)
        if right_res is not None:
            return right_res
        return self.left.find_largest_less_or_equal(x)

def build(l, r):
    node = SegmentTreeNode(l, r)
    if l == r:
        return node
    mid = (l + r) // 2
    node.left = build(l, mid)
    node.right = build(mid + 1, r)
    node.count = node.left.count + node.right.count
    node.min_val = node.left.min_val
    node.max_val = node.right.max_val
    return node

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

root = build(1, n)

total = 0
unassigned = []

for i, p in rounds:
    card = root.find_smallest_greater_than(p)
    if card is not None:
        total += i
        root.delete(card)
    else:
        unassigned.append((i, p))

unassigned.sort(key=lambda x: -x[1])

for i, p in unassigned:
    card = root.find_largest_less_or_equal(p)
    if card is not None:
        if card < p:
            total -= i
        root.delete(card)

print(total)
0