結果

問題 No.1079 まお
ユーザー lam6er
提出日時 2025-04-15 21:04:48
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,198 bytes
コンパイル時間 448 ms
コンパイル使用メモリ 82,344 KB
実行使用メモリ 183,680 KB
最終ジャッジ日時 2025-04-15 21:10:17
合計ジャッジ時間 9,560 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 12 WA * 13 TLE * 1 -- * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect
from collections import defaultdict

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    n = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:2+n]))
    A = [0] + A  # 1-based indexing

    # Precompute log_table for Sparse Table
    log_table = [0] * (n + 2)
    for i in range(2, n + 2):
        log_table[i] = log_table[i // 2] + 1
    k_max = log_table[n] if n >= 1 else 0

    # Build Sparse Table for RMQ
    st = []
    st.append(A.copy())
    for k in range(1, k_max + 1):
        st_k = []
        length = 1 << (k - 1)
        for i in range(1, n + 1 - (1 << k) + 1):
            st_k.append(min(st[k-1][i], st[k-1][i + length]))
        st.append([0] * (n + 1))
        for i in range(len(st_k)):
            st[k][i + 1] = st_k[i]

    def get_min(l, r):
        if l > r:
            return float('inf')
        length = r - l + 1
        k = log_table[length] - 1
        if k < 0:
            return st[0][l]
        return min(st[k][l], st[k][r - (1 << k) + 1])

    # Preprocess positions
    pos_map = defaultdict(list)
    for i in range(1, n + 1):
        pos_map[A[i]].append(i)

    ans = 0

    for x in range(n):
        pos = x + 1
        if pos > n:
            continue
        a = A[pos]
        v = K - a
        if v not in pos_map:
            continue
        i_list = pos_map[v]
        # Find i >= pos
        left_idx = bisect.bisect_left(i_list, pos)
        for i in i_list[left_idx:]:
            if i < pos:
                continue  # shouldn't happen due to bisect
            # Check x + y <= n-1 where y = n - i
            if x + (n - i) > n - 1:
                continue
            l = pos
            r = i
            min_val = get_min(l, r)
            # Check occurrence of min_val in [l, r]
            min_positions = pos_map.get(min_val, [])
            # Find left and right bounds in min_positions
            left_min = bisect.bisect_left(min_positions, l)
            right_min = bisect.bisect_right(min_positions, r)
            count = right_min - left_min
            if count == 1:
                ans += (r - l + 1)
    print(ans)

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