結果
問題 |
No.1079 まお
|
ユーザー |
![]() |
提出日時 | 2025-04-15 21:03:13 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,923 bytes |
コンパイル時間 | 526 ms |
コンパイル使用メモリ | 82,152 KB |
実行使用メモリ | 116,524 KB |
最終ジャッジ日時 | 2025-04-15 21:08:11 |
合計ジャッジ時間 | 9,832 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 25 TLE * 1 -- * 4 |
ソースコード
import bisect from collections import defaultdict def main(): import sys input = sys.stdin.read data = input().split() idx = 0 N = int(data[idx]) idx += 1 K = int(data[idx]) idx += 1 A = list(map(int, data[idx:idx+N])) idx += N value_indices = defaultdict(list) for i in range(N): value_indices[A[i]].append(i) class SegmentTree: def __init__(self, data): self.n = len(data) self.size = 1 while self.size < self.n: self.size <<= 1 self.min_val = [float('inf')] * (2 * self.size) self.count = [0] * (2 * self.size) for i in range(self.n): self.min_val[self.size + i] = data[i] self.count[self.size + i] = 1 for i in range(self.size - 1, 0, -1): left_min = self.min_val[2 * i] right_min = self.min_val[2 * i + 1] if left_min < right_min: self.min_val[i] = left_min self.count[i] = self.count[2 * i] elif right_min < left_min: self.min_val[i] = right_min self.count[i] = self.count[2 * i + 1] else: self.min_val[i] = left_min self.count[i] = self.count[2 * i] + self.count[2 * i + 1] def query(self, l, r): res_min = float('inf') res_count = 0 l += self.size r += self.size while l <= r: if l % 2 == 1: current_min = self.min_val[l] current_count = self.count[l] if current_min < res_min: res_min = current_min res_count = current_count elif current_min == res_min: res_count += current_count l += 1 if r % 2 == 0: current_min = self.min_val[r] current_count = self.count[r] if current_min < res_min: res_min = current_min res_count = current_count elif current_min == res_min: res_count += current_count r -= 1 l >>= 1 r >>= 1 return (res_min, res_count) st = SegmentTree(A) total = 0 for i in range(N): target = K - A[i] if target not in value_indices: continue indices = value_indices[target] pos = bisect.bisect_left(indices, i) for j in indices[pos:]: if j < i: continue min_val, count = st.query(i, j) if count == 1: total += (j - i + 1) print(total) if __name__ == '__main__': main()