結果

問題 No.1079 まお
ユーザー gew1fw
提出日時 2025-06-12 20:01:19
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,584 bytes
コンパイル時間 234 ms
コンパイル使用メモリ 81,852 KB
実行使用メモリ 117,912 KB
最終ジャッジ日時 2025-06-12 20:04:57
合計ジャッジ時間 9,561 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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_tree = [float('inf')] * (2 * self.size)
        # Fill leaves
        for i in range(self.n):
            self.min_tree[self.size + i] = data[i]
        # Build the tree
        for i in range(self.size - 1, 0, -1):
            self.min_tree[i] = min(self.min_tree[2 * i], self.min_tree[2 * i + 1])
    
    def query_min(self, l, r):
        # [l, r) interval
        res = float('inf')
        l += self.size
        r += self.size
        while l < r:
            if l % 2 == 1:
                res = min(res, self.min_tree[l])
                l += 1
            if r % 2 == 1:
                r -= 1
                res = min(res, self.min_tree[r])
            l >>= 1
            r >>= 1
        return res

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
    
    val_to_indices = dict()
    for i in range(n):
        val = a[i]
        if val not in val_to_indices:
            val_to_indices[val] = []
        val_to_indices[val].append(i)
    
    seg_tree = SegmentTree(a)
    
    answer = 0
    
    for j in range(n):
        target = k - a[j]
        if target not in val_to_indices:
            continue
        indices = val_to_indices[target]
        # Find all i in indices where i <= j
        # Since indices are sorted, use bisect
        pos = bisect.bisect_right(indices, j)
        for i in indices[:pos]:
            if i > j:
                continue
            # Query min in [i, j]
            min_val = seg_tree.query_min(i, j + 1)
            # Check if min_val occurs exactly once in [i, j]
            if min_val not in val_to_indices:
                continue
            m_indices = val_to_indices[min_val]
            # Find the first index >=i and <=j
            left = bisect.bisect_left(m_indices, i)
            if left >= len(m_indices):
                continue
            first = m_indices[left]
            if first > j:
                continue
            # Find the last index <=j
            right = bisect.bisect_right(m_indices, j) - 1
            if right < left:
                continue
            last = m_indices[right]
            if first == last:
                length = j - i + 1
                answer += length
    
    print(answer)

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