Problem p03641 (python)

Fixed submission:
def main():
    n = int(input())
    p = list(map(lambda x: int(x)-1, input().split()))

    pos = [j for i, j in sorted([(j, i) for i, j in enumerate(p)])]
    basesize = n >> 1
    num = 1
    while num < basesize:
        num *= 2
    num -= 1

    tree_even = [100001]*(num*2+1)
    tree_odd = [100001]*(num*2+1)

    for i in range(num, num+basesize):
        tree_even[i] = p[(i-num)*2]
    for i in range(num-1, -1, -1):
        tree_even[i] = min(tree_even[2*i+1:2*i+3])
    for i in range(num, num+basesize):
        tree_odd[i] = p[(i-num)*2+1]
    for i in range(num-1, -1, -1):
        tree_odd[i] = min(tree_odd[2*i+1:2*i+3])

    g = dict()
    d = dict()
    q = [n-1]
    qap, qp = q.append, q.pop
    while q:
        t = qp()
        m, M = t//n, t % n
        if m+1 == M:
            d[t] = p[m]*n+p[M]
            continue
        g[t] = []
        gap = g[t].append
        if m % 2 == 0:
            i1, j1 = m >> 1, (M >> 1)+1
            even = 200000
            l, r = i1+num, j1+num
            while l < r:
                if r % 2 == 0:
                    r -= 1
                    even = min(even, tree_even[r])
                if l % 2 == 0:
                    even = min(even, tree_even[l])
                    l += 1
                l >>= 1
                r >>= 1
            even_idx = pos[even]
            odd = 200000
            l, r = (even_idx >> 1)+num, j1+num
            while l < r:
                if r % 2 == 0:
                    r -= 1
                    odd = min(odd, tree_odd[r])
                if l % 2 == 0:
                    odd = min(odd, tree_odd[l])
                    l += 1
                l >>= 1
                r >>= 1
            odd_idx = pos[odd]
            d[t] = even*n+odd
            if m != even_idx:
                s = m*n+even_idx-1
                qap(s)
                gap(s)
            if M != odd_idx:
                s = (odd_idx+1)*n+M
                qap(s)
                gap(s)
            if even_idx+1 != odd_idx:
                s = (even_idx+1)*n+odd_idx-1
                qap(s)
                gap(s)
        else:
            i1, j1 = m >> 1, M >> 1
            odd = 200000
            l, r = i1+num, j1+num
            while l < r:
                if r % 2 == 0:
                    r -= 1
                    odd = min(odd, tree_odd[r])
                if l % 2 == 0:
                    odd = min(odd, tree_odd[l])
                    l += 1
                l >>= 1
                r >>= 1
            odd_idx = pos[odd]
            even = 200000
            l, r = (odd_idx >> 1)+1+num, j1+1+num
            while l < r:
                if r % 2 == 0:
                    r -= 1
                    even = min(even, tree_even[r])
                if l % 2 == 0:
                    even = min(even, tree_even[l])
                    l += 1
                l >>= 1
                r >>= 1
            even_idx = pos[even]
            d[t] = odd*n+even
            if m != odd_idx:
                s = m*n+odd_idx-1
                qap(s)
                gap(s)
            if M != even_idx:
                s = (even_idx+1)*n+M
                qap(s)
                gap(s)
            if odd_idx+1 != even_idx:
                s = (odd_idx+1)*n+even_idx-1
                qap(s)
                gap(s)

    g2 = dict()

    for i, t in g.items():
        k = d[i]
        g2[k] = []
        ga = g2[k].append
        for j in t:
            ga(d[j])

    import heapq
    h = [d[n-1]]
    heapq.heapify(h)
    ans = []
    hpop = heapq.heappop
    hpush = heapq.heappush

    while h:
        t = hpop(h)
        ans += [t//n+1, t % n+1]
        if t in g2:
            for s in g2[t]:
                hpush(h, s)

    print(*ans)


main()

Buggy submission (verdict: Runtime Error):
def main():
    n = int(input())
    p = list(map(lambda x: int(x)-1, input().split()))
    pos = [j for i, j in sorted([(j, i) for i, j in enumerate(p)])]

    class segtree():
        def __init__(self, base, monoid, ini):  # self,モノイド,元の配列
            # ini：上限（下限）,base：元の配列,monoid：モノイド,tree：セグ木,depth：treeの深さ,
            # basesize：baseの要素数,treesize：treeの要素数,num：treesize-basesize
            # 初期値（上限とか下限）を決定
            self.ini = ini
            # セグ木の要素数（num）および深さ（depth）を計算
            self.basesize = len(base)
            num, depth, basesize = 1, 1, self.basesize
            while num < basesize:
                num *= 2
                depth += 1
            num -= 1
            self.num, self.depth = num, depth
            # 関数（モノイド、今回はmin）を設定
            self.monoid = monoid
            # セグ木を構築
            self.treesize = num*2+1
            self.tree = [None]*self.treesize
            tree = self.tree
            # segtree[m]以降に代入したい配列を入力していく
            for i in range(num, num+basesize):
                tree[i] = base[i-num]
            for i in range(num+basesize, self.treesize):
                tree[i] = ini
            # segtree[m]以降の情報を使って、0に向かってセグ木を構築していく
            for i in range(num-1, -1, -1):
                tree[i] = monoid(tree[2*i+1], tree[2*i+2])

        # 半開区間[lower,upper)の最小値（とか）を探す関数
        def search(self, lower, upper):
            # 返り値を初期化
            ret, num = self.ini, self.num
            l, r, monoid, tree = lower+num, upper+num, self.monoid, self.tree
            while l < r:
                if r % 2 == 0:
                    r -= 1
                    ret = monoid(ret, tree[r])
                if l % 2 == 0:
                    ret = monoid(ret, tree[l])
                    l += 1
                l //= 2
                r //= 2
            return ret

    seg_even = segtree(p[::2], min, n+1)
    seg_odd = segtree(p[1::2], min, n+1)

    g = dict()
    d = dict()
    q = [(0, n-1)]
    qap = q.append
    while q:
        m, M = q.pop()
        g[(m, M)] = []
        gap = g[(m, M)].append
        if m % 2 == 0:
            i1, j1 = m//2, M//2+1
            even = seg_even.search(i1, j1)
            odd = seg_odd.search(i1, j1)
            even_idx, odd_idx = pos[even], pos[odd]
            d[(m, M)] = (even+1, odd+1)
            if m != even_idx:
                qap((m, even_idx-1))
                gap((m, even_idx-1))
            if M != odd_idx:
                qap((odd_idx+1, M))
                gap((odd_idx+1, M))
            if even_idx+1 != odd_idx:
                qap((even_idx+1, odd_idx-1))
                gap((even_idx+1, odd_idx-1))
        else:
            i1, j1 = m//2, M//2
            odd = seg_odd.search(i1, j1)
            even = seg_even.search(i1+1, j1+1)
            even_idx, odd_idx = pos[even], pos[odd]
            d[(m, M)] = (odd+1, even+1)
            if m != odd_idx:
                qap((m, odd_idx-1))
                gap((m, odd_idx-1))
            if M != even_idx:
                qap((even_idx+1, M))
                gap((even_idx+1, M))
            if odd_idx+1 != even_idx:
                qap((odd_idx+1, even_idx-1))
                gap((odd_idx+1, even_idx-1))

    import heapq
    x, y = d[(0, n-1)]
    h = [(x, y, 0, n-1)]
    heapq.heapify(h)
    ans = []

    while h:
        x, y, t1, t2 = heapq.heappop(h)
        i, j = d[(t1, t2)]
        ans += [x, y]
        for a, b in g[(t1, t2)]:
            e, f = d[(a, b)]
            heapq.heappush(h, (e, f, a, b))

    print(*ans)


main()