結果

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

ソースコード

diff # 

import sys
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()))
    
    # Segment Tree Node
    class Node:
        __slots__ = ['l', 'r', 'left', 'right', 'min_val', 'count']
        def __init__(self, l, r):
            self.l = l
            self.r = r
            self.left = None
            self.right = None
            self.min_val = 0
            self.count = 0

    # Build Segment Tree
    def build(l, r):
        node = Node(l, r)
        if l == r:
            node.min_val = A[l]
            node.count = 1
            return node
        mid = (l + r) // 2
        node.left = build(l, mid)
        node.right = build(mid+1, r)
        if node.left.min_val < node.right.min_val:
            node.min_val = node.left.min_val
            node.count = node.left.count
        elif node.right.min_val < node.left.min_val:
            node.min_val = node.right.min_val
            node.count = node.right.count
        else:
            node.min_val = node.left.min_val
            node.count = node.left.count + node.right.count
        return node

    root = build(0, N-1)

    # Query Segment Tree
    def query(node, l, r):
        if node.r < l or node.l > r:
            return (float('inf'), 0)
        if l <= node.l and node.r <= r:
            return (node.min_val, node.count)
        left_min, left_cnt = query(node.left, l, r)
        right_min, right_cnt = query(node.right, l, r)
        if left_min < right_min:
            return (left_min, left_cnt)
        elif right_min < left_min:
            return (right_min, right_cnt)
        else:
            return (left_min, left_cnt + right_cnt)

    # Precompute value to indices
    value_map = defaultdict(list)
    for idx, val in enumerate(A):
        value_map[val].append(idx)
    
    answer = 0

    for i in range(N):
        target = K - A[i]
        if target not in value_map:
            continue
        for j in value_map[target]:
            if j < i:
                continue
            min_val, cnt = query(root, i, j)
            if cnt == 1:
                answer += (j - i + 1)
    
    print(answer)

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