結果

問題 No.1079 まお
コンテスト
ユーザー gew1fw
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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