結果
問題 |
No.1687 What the Heck?
|
ユーザー |
![]() |
提出日時 | 2025-04-16 15:27:26 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,147 bytes |
コンパイル時間 | 506 ms |
コンパイル使用メモリ | 81,592 KB |
実行使用メモリ | 109,764 KB |
最終ジャッジ日時 | 2025-04-16 15:29:16 |
合計ジャッジ時間 | 6,823 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 1 WA * 17 |
ソースコード
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)