Problem p03641 (python)

Fixed submission:
class segment_tree:
    def __init__(self, N, operator_M, e_M):
        self.op_M = operator_M
        self.e_M = e_M
        
        self.N0 = 1<<(N-1).bit_length()
        self.dat = [self.e_M]*(2*self.N0)
    
    # 長さNの配列 initial で初期化
    def build(self, initial):
        self.dat[self.N0:self.N0+len(initial)] = initial[:]
        for k in range(self.N0-1,0,-1):
            self.dat[k] = self.op_M(self.dat[2*k], self.dat[2*k+1])

    # a_k の値を x に更新
    def update(self,k,x):
        k += self.N0
        self.dat[k] = x
        k //= 2
        while k:
            self.dat[k] = self.op_M(self.dat[2*k], self.dat[2*k+1])
            k //= 2

    # 区間[L,R]をopでまとめる
    def query(self,L,R):
        L += self.N0; R += self.N0 + 1 
        sl = sr = self.e_M
        while L < R:
            if R & 1:
                R -= 1
                sr = self.op_M(self.dat[R],sr)
            if L & 1:
                sl = self.op_M(sl,self.dat[L])
                L += 1
            L >>= 1; R >>= 1
        return self.op_M(sl,sr)

    def get(self, k): #k番目の値を取得。query[k,k]と同じ
        return self.dat[k+self.N0]

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline
sys.setrecursionlimit(10**5)

n,*p = map(int,read().split())

INF = 1<<30
p += [INF,INF]

def argmin(i,j):
    if p[i] < p[j]: return i
    else: return j

even = segment_tree(n//2+1,argmin,n)
odd = segment_tree(n//2+1,argmin,n+1)

even.build(range(0,n+2,2))
odd.build(range(1,n+2,2))

ans = [0]*n

def get(i,j):
    return odd.query(i//2,(j-1)//2)  if i%2 else even.query(i//2,(j-1)//2)

from heapq import *
k = get(0,n-1)
q = [(p[k],k,0,n-1)]

for I in range(n//2):
    v,k,i,j = heappop(q)
    l = even.query((k+1)//2,j//2) if i%2 else odd.query((k+1)//2,j//2)
    
    #print(v,p[l])
        
    ans[2*I] = v
    ans[2*I+1] = p[l]
    
    if i < k+1:
        kk = get(i,k-1)
        heappush(q,(p[kk],kk,i,k-1))
    if k+1<l-1:
        kk = get(k+1,l-1)
        heappush(q,(p[kk],kk,k+1,l-1))
    if l+1 < j:
        kk = get(l+1,j)
        heappush(q,(p[kk],kk,l+1,j))
    
print(*ans)



#x = merge3([[1,0],[4,0]],[[2,0]],[[3,0],[6,0]])
#print(x)

Buggy submission (verdict: Runtime Error):
class segment_tree:
    def __init__(self, N, operator_M, e_M):
        self.op_M = operator_M
        self.e_M = e_M
        
        self.N0 = 1<<(N-1).bit_length()
        self.dat = [self.e_M]*(2*self.N0)
    
    # 長さNの配列 initial で初期化
    def build(self, initial):
        self.dat[self.N0:self.N0+len(initial)] = initial[:]
        for k in range(self.N0-1,0,-1):
            self.dat[k] = self.op_M(self.dat[2*k], self.dat[2*k+1])

    # a_k の値を x に更新
    def update(self,k,x):
        k += self.N0
        self.dat[k] = x
        k //= 2
        while k:
            self.dat[k] = self.op_M(self.dat[2*k], self.dat[2*k+1])
            k //= 2

    # 区間[L,R]をopでまとめる
    def query(self,L,R):
        L += self.N0; R += self.N0 + 1 
        sl = sr = self.e_M
        while L < R:
            if R & 1:
                R -= 1
                sr = self.op_M(self.dat[R],sr)
            if L & 1:
                sl = self.op_M(sl,self.dat[L])
                L += 1
            L >>= 1; R >>= 1
        return self.op_M(sl,sr)

    def get(self, k): #k番目の値を取得。query[k,k]と同じ
        return self.dat[k+self.N0]

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,*p = map(int,read().split())

INF = 1<<30
p += [INF,INF]

def argmin(i,j):
    if p[i] < p[j]: return i
    else: return j

even = segment_tree(n//2+1,argmin,n)
odd = segment_tree(n//2+1,argmin,n+1)

#print(p[::2],n//2)
even.build(range(0,n+2,2))
odd.build(range(1,n+2,2))

#print(p)
#print(even.dat)
#print(odd.dat)


def merge(a,b):
    la,lb = len(a),len(b)
    res = [0]*(la+lb)
    ia = ib = 0
    for i in range(la+lb):
        if ib==lb:
            res[i:] = a[ia:]
            return res
        if ia==la:
            res[i:] = b[ib:]
            return res
        if a[ia] < b[ib]:
            res[i] = a[ia]
            ia += 1
        else:
            res[i] = b[ib]
            ib += 1
    return res

def merge3(l0,l1,l2):
    if len(l0) < len(l1):
        if len(l1) < len(l2):
            return merge(merge(l0,l1),l2)
        else:    
            return merge(merge(l0,l2),l1)
    else:    
        if len(l0) < len(l2):
            return merge(merge(l0,l1),l2)
        else:    
            return merge(merge(l1,l2),l0)


def f(i,j):
    if i >= j: return []
    if i+1==j: return [(p[i],p[j])]

    k = odd.query(i//2,(j-1)//2)  if i%2 else even.query(i//2,(j-1)//2)
    l = even.query((k+1)//2,j//2) if i%2 else odd.query((k+1)//2,j//2)
    res = [(p[k],p[l])] + merge3(f(i,k-1), f(k+1,l-1), f(l+1,j))
    
    #print(f"i={i},j={j},k={k},l={l},{res}")
    
    return res

#print(p)
r = f(0,n-1)

ans = []
for lst in r:
    ans += [lst[0],lst[1]]

print(*ans)