結果
問題 |
No.1079 まお
|
ユーザー |
![]() |
提出日時 | 2025-06-12 18:14:54 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,662 bytes |
コンパイル時間 | 177 ms |
コンパイル使用メモリ | 81,900 KB |
実行使用メモリ | 122,828 KB |
最終ジャッジ日時 | 2025-06-12 18:15:41 |
合計ジャッジ時間 | 11,089 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 25 TLE * 1 -- * 4 |
ソースコード
import bisect from collections import defaultdict def main(): import sys 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 # Compute L and R for each index def compute_left(A): n = len(A) L = [-1] * n stack = [] for i in range(n): while stack and A[stack[-1]] >= A[i]: stack.pop() if stack: L[i] = stack[-1] else: L[i] = -1 stack.append(i) return L def compute_right(A): n = len(A) R = [n] * n stack = [] for i in range(n-1, -1, -1): while stack and A[stack[-1]] > A[i]: stack.pop() if stack: R[i] = stack[-1] else: R[i] = n stack.append(i) return R L = compute_left(A) R = compute_right(A) # Build position map pos_map = defaultdict(list) for idx, num in enumerate(A): pos_map[num].append(idx) for num in pos_map: pos_map[num].sort() # Build m_pos (positions for each A[k]) m_pos = defaultdict(list) for idx, num in enumerate(A): m_pos[num].append(idx) for num in m_pos: m_pos[num].sort() ans = 0 for k in range(N): m = A[k] left_i = L[k] + 1 right_j = R[k] - 1 if left_i > k: continue # no i in range # i ranges from left_i to k for i in range(left_i, k + 1): target = K - A[i] if target not in pos_map: continue j_min = max(i, k) j_max = right_j if j_min > j_max: continue # Find all j in pos_map[target] where j_min <= j <= j_max j_list = pos_map[target] # Find left and right in j_list l = bisect.bisect_left(j_list, j_min) r = bisect.bisect_right(j_list, j_max) for j_idx in range(l, r): j = j_list[j_idx] if j < k: continue # j must be >=k # Check if in [i, j], m occurs exactly once and it's at k # Check m's positions in [i, j] m_list = m_pos[m] ml = bisect.bisect_left(m_list, i) mr = bisect.bisect_right(m_list, j) count = mr - ml if count == 1 and m_list[ml] == k: ans += (j - i + 1) print(ans) if __name__ == "__main__": main()