結果

問題 No.1079 まお
ユーザー lam6er
提出日時 2025-03-31 17:22:04
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,378 bytes
コンパイル時間 214 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 179,412 KB
最終ジャッジ日時 2025-03-31 17:23:16
合計ジャッジ時間 11,147 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 25 TLE * 1 -- * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from bisect import bisect_left, bisect_right
from collections import defaultdict

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N, K = int(input[ptr]), int(input[ptr+1])
    ptr +=2
    A = list(map(int, input[ptr:ptr+N]))
    ptr +=N

    # Precompute Sparse Table for Range Minimum Query
    max_level = 0
    while (1 << max_level) <= N:
        max_level +=1
    # Sparse Table storing (value, index)
    st = []
    st.append([(A[i], i) for i in range(N)])
    for k in range(1, max_level):
        prev = st[k-1]
        current = []
        length = 1 << (k-1)
        for i in range(N - (1<<k) +1):
            left = prev[i]
            right = prev[i + length]
            if left[0] <= right[0]:
                current.append(left)
            else:
                current.append(right)
        st.append(current)
    
    def get_min(l, r):
        if l > r:
            return (float('inf'), -1)
        length = r - l +1
        k = length.bit_length() -1
        if (1 <<k) > length:
            k -=1
        a = st[k][l]
        b = st[k][r - (1<<k) +1]
        return min(a, b)
    
    # Precompute the positions for each value
    pos = defaultdict(list)
    for idx, val in enumerate(A):
        pos[val].append(idx)
    
    ans = 0

    # Handle single element subarrays where 2*A[i] = K
    if K %2 ==0:
        half = K//2
        count = len(pos.get(half, []))
        ans += count
    
    # Handle subarrays of length >=2
    for i in range(N):
        required = K - A[i]
        if required not in pos:
            continue
        j_list = pos[required]
        # Find j such that j >i (since j >=i+1)
        # Using bisect_left to find the first index >=i+1
        idx = bisect_left(j_list, i+1)
        for j in j_list[idx:]:
            if j >=N:
                continue
            # Ensure j >i to have length >=2
            if j <=i:
                continue
            min_val, min_idx = get_min(i, j)
            # Count occurrences of min_val in [i, j]
            min_occurrences = pos.get(min_val, [])
            # Find the number of elements in [i, j]
            left = bisect_left(min_occurrences, i)
            right = bisect_right(min_occurrences, j)
            cnt = right - left
            if cnt ==1:
                ans += (j -i +1)
    print(ans)

if __name__ == "__main__":
    main()
0