結果

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

ソースコード

diff # 

import bisect
from collections import defaultdict

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

    # Compute L and R for each index
    def compute_left(A):
        n = len(A)
        L = [-1] * n
        stack = []
        for i in range(n):
            while stack and A[stack[-1]] >= A[i]:
                stack.pop()
            if stack:
                L[i] = stack[-1]
            else:
                L[i] = -1
            stack.append(i)
        return L

    def compute_right(A):
        n = len(A)
        R = [n] * n
        stack = []
        for i in range(n-1, -1, -1):
            while stack and A[stack[-1]] > A[i]:
                stack.pop()
            if stack:
                R[i] = stack[-1]
            else:
                R[i] = n
            stack.append(i)
        return R

    L = compute_left(A)
    R = compute_right(A)

    # Build position map
    pos_map = defaultdict(list)
    for idx, num in enumerate(A):
        pos_map[num].append(idx)
    for num in pos_map:
        pos_map[num].sort()

    # Build m_pos (positions for each A[k])
    m_pos = defaultdict(list)
    for idx, num in enumerate(A):
        m_pos[num].append(idx)
    for num in m_pos:
        m_pos[num].sort()

    ans = 0

    for k in range(N):
        m = A[k]
        left_i = L[k] + 1
        right_j = R[k] - 1
        if left_i > k:
            continue  # no i in range
        # i ranges from left_i to k
        for i in range(left_i, k + 1):
            target = K - A[i]
            if target not in pos_map:
                continue
            j_min = max(i, k)
            j_max = right_j
            if j_min > j_max:
                continue
            # Find all j in pos_map[target] where j_min <= j <= j_max
            j_list = pos_map[target]
            # Find left and right in j_list
            l = bisect.bisect_left(j_list, j_min)
            r = bisect.bisect_right(j_list, j_max)
            for j_idx in range(l, r):
                j = j_list[j_idx]
                if j < k:
                    continue  # j must be >=k
                # Check if in [i, j], m occurs exactly once and it's at k
                # Check m's positions in [i, j]
                m_list = m_pos[m]
                ml = bisect.bisect_left(m_list, i)
                mr = bisect.bisect_right(m_list, j)
                count = mr - ml
                if count == 1 and m_list[ml] == k:
                    ans += (j - i + 1)
    print(ans)

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