結果
問題 |
No.1079 まお
|
ユーザー |
![]() |
提出日時 | 2025-06-12 18:08:17 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,925 bytes |
コンパイル時間 | 573 ms |
コンパイル使用メモリ | 82,172 KB |
実行使用メモリ | 179,932 KB |
最終ジャッジ日時 | 2025-06-12 18:10:17 |
合計ジャッジ時間 | 9,717 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 25 TLE * 1 -- * 4 |
ソースコード
import sys import bisect from math import log2, floor from collections import defaultdict def main(): N, K = map(int, sys.stdin.readline().split()) A = list(map(int, sys.stdin.readline().split())) # Preprocess the positions of each value pos_dict = defaultdict(list) for idx, val in enumerate(A): pos_dict[val].append(idx) # Build sparse table for range minimum query max_log = floor(log2(N)) + 1 if N > 0 else 0 st = [] st.append(A.copy()) for k in range(1, max_log + 1): current = [] length = 1 << (k - 1) for i in range(N - (1 << k) + 1): val = min(st[k-1][i], st[k-1][i + length]) current.append(val) st.append(current) def get_min(l, r): if l > r: return float('inf') length = r - l + 1 k = length.bit_length() - 1 if (1 << k) > length: k -= 1 return min(st[k][l], st[k][r - (1 << k) + 1]) total = 0 for x in range(N): target = K - A[x] if target not in pos_dict: continue j_list = pos_dict[target] # Find the first j >= x idx = bisect.bisect_left(j_list, x) for j in j_list[idx:]: if j < x: continue # should not happen due to bisect if j >= N: break # Now check the subarray [x, j] min_val = get_min(x, j) # Get all positions of min_val if min_val not in pos_dict: continue positions = pos_dict[min_val] # Find the first position >= x and <= j left = bisect.bisect_left(positions, x) right = bisect.bisect_right(positions, j) count = right - left if count == 1: total += (j - x + 1) print(total) if __name__ == "__main__": main()