题解 | 最小前缀pypy3加二分查找勉强不超时

import sys
import bisect


def find_min_x():
    # 快速读取输入（sys.stdin.read 比 input() 快10倍以上）
    data = sys.stdin.read().split()
    idx = 0
    n = int(data[idx])
    idx += 1
    m = int(data[idx])
    idx += 1
    k = int(data[idx])
    idx += 1

    # 存储 (数值, 原始位置)，原始位置从1开始（题目要求前x个数）
    arr = []
    for i in range(n):
        val = int(data[idx])
        idx += 1
        arr.append((val, i + 1))  # 位置是1-based

    # 按数值排序（这是O(n log n)，无法优化，是必要步骤）
    arr.sort()

    min_x = float("inf")
    left = 0
    # 维护一个有序的位置列表（始终升序）
    sorted_pos = []

    # 右指针遍历，滑动窗口（O(n) 总时间）
    for right in range(n):
        # 1. 将当前元素的位置插入有序列表（二分插入，O(log n)）
        val_r, pos_r = arr[right]
        bisect.insort(sorted_pos, pos_r)

        # 2. 保证窗口内数值差 ≤k，左指针右移时删除对应位置
        while val_r - arr[left][0] > k:
            val_l, pos_l = arr[left]
            # 从有序列表中删除左指针位置（二分查找+删除，O(log n)）
            pos_idx = bisect.bisect_left(sorted_pos, pos_l)
            if pos_idx < len(sorted_pos) and sorted_pos[pos_idx] == pos_l:
                del sorted_pos[pos_idx]
            left += 1

        # 3. 当有序位置列表长度 ≥m 时，找最小的最大位置
        window_len = len(sorted_pos)
        if window_len >= m:
            # 有序列表中，第i个位置到i+m-1个位置的最大位置是 sorted_pos[i+m-1]
            # 最小的最大位置就是 sorted_pos[m-1]（因为列表升序，最左边的m个位置的最大位置最小）
            current_max_pos = sorted_pos[m - 1]
            if current_max_pos < min_x:
                min_x = current_max_pos

    # 输出结果
    print(min_x if min_x != float("inf") else -1)


if __name__ == "__main__":
    find_min_x()