結果
問題 |
No.1687 What the Heck?
|
ユーザー |
![]() |
提出日時 | 2025-04-15 20:59:26 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,540 bytes |
コンパイル時間 | 484 ms |
コンパイル使用メモリ | 82,512 KB |
実行使用メモリ | 135,100 KB |
最終ジャッジ日時 | 2025-04-15 21:03:15 |
合計ジャッジ時間 | 6,264 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 8 WA * 10 |
ソースコード
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()