結果

問題 No.1079 まお
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 12:53:34
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,925 bytes
コンパイル時間 425 ms
コンパイル使用メモリ 82,236 KB
実行使用メモリ 180,252 KB
最終ジャッジ日時 2025-06-12 12:55:57
合計ジャッジ時間 9,887 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 25 TLE * 1 -- * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0