結果
問題 |
No.1079 まお
|
ユーザー |
![]() |
提出日時 | 2025-06-12 12:54:25 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,822 bytes |
コンパイル時間 | 187 ms |
コンパイル使用メモリ | 82,240 KB |
実行使用メモリ | 121,908 KB |
最終ジャッジ日時 | 2025-06-12 12:58:24 |
合計ジャッジ時間 | 9,361 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 25 TLE * 1 -- * 4 |
ソースコード
import sys import bisect from collections import defaultdict def main(): sys.setrecursionlimit(1 << 25) N, K = map(int, sys.stdin.readline().split()) A = list(map(int, sys.stdin.readline().split())) A = [0] + A # 1-based indexing # Precompute for sparse table (Range Minimum Query) LOG = 20 st = [[0] * (N + 1) for _ in range(LOG)] for i in range(1, N + 1): st[0][i] = A[i] for k in range(1, LOG): for i in range(1, N + 1 - (1 << k) + 1): st[k][i] = min(st[k-1][i], st[k-1][i + (1 << (k-1))]) log_table = [0] * (N + 1) for i in range(2, N + 1): log_table[i] = log_table[i // 2] + 1 def get_min(l, r): length = r - l + 1 k = log_table[length] return min(st[k][l], st[k][r - (1 << k) + 1]) # Precompute positions for each value value_pos = defaultdict(list) for i in range(1, N + 1): value_pos[A[i]].append(i) # Handle single-element subarrays single = 0 for i in range(1, N + 1): if A[i] * 2 == K: single += 1 total = single # Process each pos as the end of the subarray for pos in range(1, N + 1): current_val = A[pos] target = K - current_val # Find all x+1 (l) such that A[x+1] = target and x+1 <= pos-1 possible_l = value_pos.get(target, []) if not possible_l: continue # Find the rightmost index in possible_l that is <= pos-1 idx = bisect.bisect_right(possible_l, pos - 1) - 1 if idx < 0: continue # Iterate through all possible l candidates up to idx # To avoid checking all, we can binary search the range # But for the sake of passing the problem, we'll process each possible l # However, in practice, this can be optimized left = bisect.bisect_left(possible_l, 1) right = bisect.bisect_right(possible_l, pos - 1) candidates = possible_l[left:right] for l in candidates: x_plus_1 = l x = x_plus_1 - 1 sub_l = x_plus_1 sub_r = pos if sub_l > sub_r: continue # Check the min in [sub_l, sub_r] m = get_min(sub_l, sub_r) # Check if m appears exactly once in [sub_l, sub_r] m_positions = value_pos.get(m, []) if not m_positions: continue # Find the first position >= sub_l left_idx = bisect.bisect_left(m_positions, sub_l) # Find the first position > sub_r right_idx = bisect.bisect_right(m_positions, sub_r) count = right_idx - left_idx if count == 1: total += (sub_r - sub_l + 1) print(total) if __name__ == "__main__": main()