結果
問題 |
No.1079 まお
|
ユーザー |
![]() |
提出日時 | 2025-06-12 19:56:27 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,624 bytes |
コンパイル時間 | 246 ms |
コンパイル使用メモリ | 81,996 KB |
実行使用メモリ | 118,052 KB |
最終ジャッジ日時 | 2025-06-12 19:57:22 |
合計ジャッジ時間 | 9,193 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 25 TLE * 1 -- * 4 |
ソースコード
import sys import bisect class SegmentTree: def __init__(self, data): self.n = len(data) self.size = 1 while self.size < self.n: self.size <<= 1 self.min_val = [0] * (2 * self.size) self.count = [0] * (2 * self.size) # Initialize leaves for i in range(self.n): self.min_val[self.size + i] = data[i] self.count[self.size + i] = 1 # Initialize non-leaves for i in range(self.size - 1, 0, -1): left = 2 * i right = 2 * i + 1 if self.min_val[left] < self.min_val[right]: self.min_val[i] = self.min_val[left] self.count[i] = self.count[left] elif self.min_val[left] > self.min_val[right]: self.min_val[i] = self.min_val[right] self.count[i] = self.count[right] else: self.min_val[i] = self.min_val[left] self.count[i] = self.count[left] + self.count[right] 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: if self.min_val[l] < res_min: res_min = self.min_val[l] res_count = self.count[l] elif self.min_val[l] == res_min: res_count += self.count[l] l += 1 if r % 2 == 0: if self.min_val[r] < res_min: res_min = self.min_val[r] res_count = self.count[r] elif self.min_val[r] == res_min: res_count += self.count[r] r -= 1 l >>= 1 r >>= 1 return (res_min, res_count) def main(): input = sys.stdin.read().split() ptr = 0 N = int(input[ptr]) ptr += 1 K = int(input[ptr]) ptr += 1 A = list(map(int, input[ptr:ptr + N])) ptr += N value_indices = {} for i in range(N): val = A[i] if val not in value_indices: value_indices[val] = [] value_indices[val].append(i) st = SegmentTree(A) total = 0 for j in range(N): a_j = A[j] target = K - a_j if target not in value_indices: continue list_i = value_indices[target] idx = bisect.bisect_right(list_i, j) for i in list_i[:idx]: min_val, cnt = st.query(i, j) if cnt == 1: total += (j - i + 1) print(total) if __name__ == "__main__": main()