Problem p03641 (python)

Fixed submission:
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

# lから1つおきにみたときの最小値を求める特別製
class SparseTable:
    def __init__(self, aa):
        inf = 10 ** 16
        w = len(aa)
        h = w.bit_length()
        table = [aa] * 2 + [[inf] * w for _ in range(h - 2)]
        tablei1 = table[0]
        for i in range(2, h):
            tablei = table[i]
            shift = 1 << (i - 1)
            for j in range(w):
                rj = j + shift
                if rj >= w: break
                tablei[j] = min(tablei1[j], tablei1[rj])
            tablei1 = tablei
        self.table = table

    # [l,r)の最小値
    def min(self, l, r):
        if (r - l) % 2: r += 1
        i = (r - l).bit_length() - 1
        tablei = self.table[i]
        Lmin = tablei[l]
        Rmin = tablei[r - (1 << i)]
        if Lmin < Rmin: Rmin = Lmin
        return Rmin

def main():
    n = int(input())
    pp = LI()
    st = SparseTable(pp)
    ptoi = [0] + [i for i, p in sorted(enumerate(pp), key=lambda x: x[1])]
    # 区間偶数番目の最小値と[l,r)をヒープに
    hp = []
    heappush(hp, [st.min(0, n), 0, n])
    ans = []
    for _ in range(n // 2):
        x, l, r = heappop(hp)
        if l + 2 == r:
            ans += [pp[l], pp[l + 1]]
            continue
        xi = ptoi[x]
        y = st.min(xi + 1, r)
        yi = ptoi[y]
        if xi > l:
            heappush(hp, [st.min(l, xi), l, xi])
        if xi + 1 < yi:
            heappush(hp, [st.min(xi + 1, yi), xi + 1, yi])
        if yi < r - 1:
            heappush(hp, [st.min(yi + 1, r), yi + 1, r])
        ans += [x, y]
    print(*ans)

main()

Buggy submission (verdict: Runtime Error):
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

class SegtreeMin():
    def __init__(self, n):
        self.inf = 10 ** 16
        tree_width = 1 << (n - 1).bit_length()
        self.tree_width = tree_width
        self.tree = [self.inf] * (tree_width * 2 - 1)

    def update(self, i, a):
        seg_i = self.tree_width - 1 + i
        self.tree[seg_i] = a
        while seg_i != 0:
            seg_i = (seg_i - 1) // 2
            self.tree[seg_i] = min(self.tree[seg_i * 2 + 1], self.tree[seg_i * 2 + 2])

    def refresh(self):
        for seg_i in range(self.tree_width - 2, -1, -1):
            self.tree[seg_i] = min(self.tree[seg_i * 2 + 1], self.tree[seg_i * 2 + 2])

    # [l,r)の最小値
    def min(self, l, r, seg_i=0, segL=0, segR=-1):
        if segR == -1: segR = self.tree_width
        if r <= segL or segR <= l: return self.inf
        if l <= segL and segR <= r: return self.tree[seg_i]
        segM = (segL + segR) // 2
        ret0 = self.min(l, r, seg_i * 2 + 1, segL, segM)
        ret1 = self.min(l, r, seg_i * 2 + 2, segM, segR)
        return min(ret0, ret1)

def main():
    n = int(input())
    pp = LI()
    seg_odd = SegtreeMin(n // 2)
    seg_even = SegtreeMin(n // 2)
    ptoi = [0] + [i for i, p in sorted(enumerate(pp), key=lambda x: x[1])]
    seg_odd.tree[seg_odd.tree_width - 1:seg_odd.tree_width - 1 + n // 2] = pp[1::2]
    seg_even.tree[seg_even.tree_width - 1:seg_even.tree_width - 1 + n // 2] = pp[::2]
    seg_odd.refresh()
    seg_even.refresh()
    # 区間偶数番目の最小値と[l,r)をヒープに
    hp = []
    heappush(hp, [seg_even.min(0, n // 2), 0, n])
    ans = []
    for _ in range(n // 2):
        x, l, r = heappop(hp)
        if l + 2 == r:
            ans += [pp[l], pp[l + 1]]
            continue
        xi = ptoi[x]
        if l % 2:
            y = seg_even.min((xi + 1) // 2, r // 2 + 1)
        else:
            y = seg_odd.min((xi + 1) // 2, r // 2)
        yi = ptoi[y]
        if xi - l == 2:
            heappush(hp, [pp[l], l, xi])
        elif xi - l > 2:
            minp = seg_odd.min(l // 2, xi // 2) if l % 2 else seg_even.min(l // 2, xi // 2 + 1)
            heappush(hp, [minp, l, xi])
        if yi - xi - 1 == 2:
            heappush(hp, [pp[xi + 1], xi + 1, yi])
        elif yi - xi - 1 > 2:
            minp = seg_odd.min((xi + 1) // 2, yi // 2) if (xi + 1) % 2 else seg_even.min((xi + 1) // 2, yi // 2 + 1)
            heappush(hp, [minp, xi + 1, yi])
        if r - yi - 1 == 2:
            heappush(hp, [pp[yi + 1], yi + 1, r])
        elif r - yi - 1 > 2:
            minp = seg_odd.min((yi + 1) // 2, r // 2) if (yi + 1) % 2 else seg_even.min((yi + 1) // 2, r // 2 + 1)
            heappush(hp, [minp, yi + 1, r])
        ans += [x, y]
    print(*ans)

main()