結果

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

ソースコード

diff # 

import sys
import bisect

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.size = 1
        while self.size < self.n:
            self.size <<= 1
        self.min_val = [0] * (2 * self.size)
        self.count = [0] * (2 * self.size)
        # Initialize leaves
        for i in range(self.n):
            self.min_val[self.size + i] = data[i]
            self.count[self.size + i] = 1
        # Initialize non-leaves
        for i in range(self.size - 1, 0, -1):
            left = 2 * i
            right = 2 * i + 1
            if self.min_val[left] < self.min_val[right]:
                self.min_val[i] = self.min_val[left]
                self.count[i] = self.count[left]
            elif self.min_val[left] > self.min_val[right]:
                self.min_val[i] = self.min_val[right]
                self.count[i] = self.count[right]
            else:
                self.min_val[i] = self.min_val[left]
                self.count[i] = self.count[left] + self.count[right]

    def query(self, l, r):
        res_min = float('inf')
        res_count = 0
        l += self.size
        r += self.size
        while l <= r:
            if l % 2 == 1:
                if self.min_val[l] < res_min:
                    res_min = self.min_val[l]
                    res_count = self.count[l]
                elif self.min_val[l] == res_min:
                    res_count += self.count[l]
                l += 1
            if r % 2 == 0:
                if self.min_val[r] < res_min:
                    res_min = self.min_val[r]
                    res_count = self.count[r]
                elif self.min_val[r] == res_min:
                    res_count += self.count[r]
                r -= 1
            l >>= 1
            r >>= 1
        return (res_min, res_count)

def main():
    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

    value_indices = {}
    for i in range(N):
        val = A[i]
        if val not in value_indices:
            value_indices[val] = []
        value_indices[val].append(i)

    st = SegmentTree(A)

    total = 0
    for j in range(N):
        a_j = A[j]
        target = K - a_j
        if target not in value_indices:
            continue
        list_i = value_indices[target]
        idx = bisect.bisect_right(list_i, j)
        for i in list_i[:idx]:
            min_val, cnt = st.query(i, j)
            if cnt == 1:
                total += (j - i + 1)
    print(total)

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