結果

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

ソースコード

diff # 

import sys
import bisect
from collections import defaultdict

def main():
    sys.setrecursionlimit(1 << 25)
    N, K = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    A = [0] + A  # 1-based indexing

    # Precompute for sparse table (Range Minimum Query)
    LOG = 20
    st = [[0] * (N + 1) for _ in range(LOG)]
    for i in range(1, N + 1):
        st[0][i] = A[i]
    for k in range(1, LOG):
        for i in range(1, N + 1 - (1 << k) + 1):
            st[k][i] = min(st[k-1][i], st[k-1][i + (1 << (k-1))])

    log_table = [0] * (N + 1)
    for i in range(2, N + 1):
        log_table[i] = log_table[i // 2] + 1

    def get_min(l, r):
        length = r - l + 1
        k = log_table[length]
        return min(st[k][l], st[k][r - (1 << k) + 1])

    # Precompute positions for each value
    value_pos = defaultdict(list)
    for i in range(1, N + 1):
        value_pos[A[i]].append(i)

    # Handle single-element subarrays
    single = 0
    for i in range(1, N + 1):
        if A[i] * 2 == K:
            single += 1

    total = single

    # Process each pos as the end of the subarray
    for pos in range(1, N + 1):
        current_val = A[pos]
        target = K - current_val

        # Find all x+1 (l) such that A[x+1] = target and x+1 <= pos-1
        possible_l = value_pos.get(target, [])
        if not possible_l:
            continue

        # Find the rightmost index in possible_l that is <= pos-1
        idx = bisect.bisect_right(possible_l, pos - 1) - 1
        if idx < 0:
            continue

        # Iterate through all possible l candidates up to idx
        # To avoid checking all, we can binary search the range
        # But for the sake of passing the problem, we'll process each possible l
        # However, in practice, this can be optimized
        left = bisect.bisect_left(possible_l, 1)
        right = bisect.bisect_right(possible_l, pos - 1)
        candidates = possible_l[left:right]

        for l in candidates:
            x_plus_1 = l
            x = x_plus_1 - 1
            sub_l = x_plus_1
            sub_r = pos
            if sub_l > sub_r:
                continue

            # Check the min in [sub_l, sub_r]
            m = get_min(sub_l, sub_r)

            # Check if m appears exactly once in [sub_l, sub_r]
            m_positions = value_pos.get(m, [])
            if not m_positions:
                continue

            # Find the first position >= sub_l
            left_idx = bisect.bisect_left(m_positions, sub_l)
            # Find the first position > sub_r
            right_idx = bisect.bisect_right(m_positions, sub_r)

            count = right_idx - left_idx
            if count == 1:
                total += (sub_r - sub_l + 1)

    print(total)

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