結果

問題 No.1079 まお
ユーザー lam6er
提出日時 2025-04-16 15:25:03
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,226 bytes
コンパイル時間 255 ms
コンパイル使用メモリ 81,984 KB
実行使用メモリ 203,444 KB
最終ジャッジ日時 2025-04-16 15:25:44
合計ジャッジ時間 10,800 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 26 TLE * 1 -- * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

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

    # Calculate left[i]: nearest previous index with value < A[i]
    left = [0] * (N + 1)
    stack = []
    for i in range(1, N + 1):
        while stack and A[stack[-1]] >= A[i]:
            stack.pop()
        left[i] = stack[-1] if stack else 0
        stack.append(i)

    # Calculate right[i]: nearest next index with value < A[i]
    right = [N + 1] * (N + 1)
    stack = []
    for i in range(N, 0, -1):
        while stack and A[stack[-1]] >= A[i]:
            stack.pop()
        right[i] = stack[-1] if stack else (N + 1)
        stack.append(i)

    # Calculate prev_same[i]: last occurrence of A[i] before i
    prev_same = [0] * (N + 2)
    last_occurrence = {}
    for i in range(1, N + 1):
        prev_same[i] = last_occurrence.get(A[i], 0)
        last_occurrence[A[i]] = i

    # Calculate next_same[i]: next occurrence of A[i] after i
    next_same = [N + 1] * (N + 2)
    last_occurrence = {}
    for i in range(N, 0, -1):
        next_same[i] = last_occurrence.get(A[i], N + 1)
        last_occurrence[A[i]] = i

    ans = 0

    for i in range(1, N + 1):
        count_map = defaultdict(int)
        sum_map = defaultdict(int)
        # Determine valid L range
        L_start = max(left[i] + 1, prev_same[i] + 1)
        L_end = i
        if L_start > L_end:
            continue  # No valid L
        # Populate count_map and sum_map
        for L in range(L_start, L_end + 1):
            val = A[L]
            count_map[val] += 1
            sum_map[val] += L

        # Determine valid R range
        R_start = i
        R_end = min(right[i] - 1, next_same[i] - 1)
        if R_start > R_end:
            continue  # No valid R
        # Calculate contributions from valid R
        for R in range(R_start, R_end + 1):
            target = K - A[R]
            cnt = count_map.get(target, 0)
            if cnt:
                ans += (R + 1) * cnt - sum_map[target]

    print(ans)

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