結果

問題 No.1079 まお
コンテスト
ユーザー lam6er
提出日時 2025-04-16 15:25:52
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,923 bytes
コンパイル時間 287 ms
コンパイル使用メモリ 81,648 KB
実行使用メモリ 116,156 KB
最終ジャッジ日時 2025-04-16 15:27:47
合計ジャッジ時間 8,934 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 25 TLE * 1 -- * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect
from collections import defaultdict

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

    value_indices = defaultdict(list)
    for i in range(N):
        value_indices[A[i]].append(i)

    class SegmentTree:
        def __init__(self, data):
            self.n = len(data)
            self.size = 1
            while self.size < self.n:
                self.size <<= 1
            self.min_val = [float('inf')] * (2 * self.size)
            self.count = [0] * (2 * self.size)
            for i in range(self.n):
                self.min_val[self.size + i] = data[i]
                self.count[self.size + i] = 1
            for i in range(self.size - 1, 0, -1):
                left_min = self.min_val[2 * i]
                right_min = self.min_val[2 * i + 1]
                if left_min < right_min:
                    self.min_val[i] = left_min
                    self.count[i] = self.count[2 * i]
                elif right_min < left_min:
                    self.min_val[i] = right_min
                    self.count[i] = self.count[2 * i + 1]
                else:
                    self.min_val[i] = left_min
                    self.count[i] = self.count[2 * i] + self.count[2 * i + 1]

        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:
                    current_min = self.min_val[l]
                    current_count = self.count[l]
                    if current_min < res_min:
                        res_min = current_min
                        res_count = current_count
                    elif current_min == res_min:
                        res_count += current_count
                    l += 1
                if r % 2 == 0:
                    current_min = self.min_val[r]
                    current_count = self.count[r]
                    if current_min < res_min:
                        res_min = current_min
                        res_count = current_count
                    elif current_min == res_min:
                        res_count += current_count
                    r -= 1
                l >>= 1
                r >>= 1
            return (res_min, res_count)

    st = SegmentTree(A)
    total = 0

    for i in range(N):
        target = K - A[i]
        if target not in value_indices:
            continue
        indices = value_indices[target]
        pos = bisect.bisect_left(indices, i)
        for j in indices[pos:]:
            if j < i:
                continue
            min_val, count = st.query(i, j)
            if count == 1:
                total += (j - i + 1)

    print(total)

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