結果
問題 |
No.1079 まお
|
ユーザー |
![]() |
提出日時 | 2025-06-12 14:44:33 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,614 bytes |
コンパイル時間 | 183 ms |
コンパイル使用メモリ | 82,584 KB |
実行使用メモリ | 124,252 KB |
最終ジャッジ日時 | 2025-06-12 14:45:52 |
合計ジャッジ時間 | 8,669 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 25 TLE * 1 -- * 4 |
ソースコード
import bisect import math 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 # Precompute occurrence lists from collections import defaultdict occ = defaultdict(list) for i in range(N): occ[A[i]].append(i) # Precompute log table log_table = [0] * (N + 1) for i in range(2, N + 1): log_table[i] = log_table[i // 2] + 1 # Build sparse table for RMQ max_log = log_table[N] if N > 0 else 0 st = [[0] * N for _ in range(max_log + 1)] st[0] = A.copy() for k in range(1, max_log + 1): for i in range(N - (1 << k) + 1): st[k][i] = min(st[k-1][i], st[k-1][i + (1 << (k-1))]) def query_min(l, r): length = r - l + 1 k = log_table[length] a = st[k][l] b = st[k][r - (1 << k) + 1] return min(a, b) total = 0 for j in range(N): target = K - A[j] if target not in occ: continue lst = occ[target] pos = bisect.bisect_right(lst, j) candidates = lst[:pos] for i in candidates: m = query_min(i, j) if m not in occ: continue m_list = occ[m] left = bisect.bisect_left(m_list, i) right_pos = bisect.bisect_right(m_list, j) count = right_pos - left if count == 1: total += (j - i + 1) print(total) if __name__ == '__main__': main()