結果

問題 No.1079 まお
ユーザー lam6er
提出日時 2025-03-26 15:56:28
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,601 bytes
コンパイル時間 292 ms
コンパイル使用メモリ 82,052 KB
実行使用メモリ 171,756 KB
最終ジャッジ日時 2025-03-26 15:57:07
合計ジャッジ時間 9,718 ms
ジャッジサーバーID
（参考情報） 		judge1 / 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().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

    # Preprocessing for Range Minimum Query (Sparse Table)
    class SparseTable:
        def __init__(self, data):
            self.n = len(data)
            self.log_table = [0] * (self.n + 1)
            for i in range(2, self.n + 1):
                self.log_table[i] = self.log_table[i // 2] + 1
            self.size = self.log_table[self.n] + 1
            self.table = []
            self.table.append(data.copy())
            for k in range(1, self.size):
                current_level = []
                for i in range(self.n - (1 << k) + 1):
                    val = min(self.table[k-1][i], self.table[k-1][i + (1 << (k-1))])
                    current_level.append(val)
                self.table.append(current_level)
        
        def query_min(self, l, r):
            length = r - l + 1
            k = self.log_table[length]
            return min(self.table[k][l], self.table[k][r - (1 << k) + 1])
    
    st = SparseTable(A)

    # Build value to indices mapping
    value_to_indices = defaultdict(list)
    for idx, val in enumerate(A):
        value_to_indices[val].append(idx)
    
    total = 0

    for i in range(N):
        current_val = A[i]
        target = K - current_val
        if target < 0:
            continue  # assuming A contains non-negative integers?
        # Get all j where A[j] == target and j >= i
        j_list = value_to_indices.get(target, [])
        if not j_list:
            continue
        # Find the first j in j_list >= i
        pos = bisect.bisect_left(j_list, i)
        for j_idx in range(pos, len(j_list)):
            j = j_list[j_idx]
            if j < i:
                continue  # should not happen due to bisect
            # Check that the subarray [i, j] is valid (i <= j)
            if j >= N:
                continue  # invalid index
            # Compute the minimum in the range [i, j]
            min_val = st.query_min(i, j)
            # Get all indices of min_val and check how many are in [i, j]
            min_list = value_to_indices.get(min_val, [])
            # Find the first >= i and <= j
            left = bisect.bisect_left(min_list, i)
            right = bisect.bisect_right(min_list, j)
            count = right - left
            if count == 1:
                total += (j - i + 1)
    print(total)

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