Problem:


Score : 800 points

Problem Statement

Let N be a positive even number.

We have a permutation of (1, 2, ..., N), p = (p_1, p_2, ..., p_N).
Snuke is constructing another permutation of (1, 2, ..., N), q, following the procedure below.

First, let q be an empty sequence.
Then, perform the following operation until p becomes empty:

Select two adjacent elements in p, and call them x and y in order. Remove x and y from p (reducing the length of p by 2), and insert x and y, preserving the original order, at the beginning of q.

When p becomes empty, q will be a permutation of (1, 2, ..., N).

Find the lexicographically smallest permutation that can be obtained as q.

Constraints

N is an even number.

2 ≤ N ≤ 2 × 10^5

p is a permutation of (1, 2, ..., N).

Input

Input is given from Standard Input in the following format:

N
p_1 p_2 ... p_N

Output

Print the lexicographically smallest permutation, with spaces in between.

Sample Input 1

4
3 2 4 1

Sample Output 1

3 1 2 4

The solution above is obtained as follows:

p
q

(3, 2, 4, 1)
()

↓
↓

(3, 1)
(2, 4)

↓
↓

()
(3, 1, 2, 4)

Sample Input 2

2
1 2

Sample Output 2

1 2

Sample Input 3

8
4 6 3 2 8 5 7 1

Sample Output 3

3 1 2 7 4 6 8 5

The solution above is obtained as follows:

p
q

(4, 6, 3, 2, 8, 5, 7, 1)
()

↓
↓

(4, 6, 3, 2, 7, 1)
(8, 5)

↓
↓

(3, 2, 7, 1)
(4, 6, 8, 5)

↓
↓

(3, 1)
(2, 7, 4, 6, 8, 5)

↓
↓

()
(3, 1, 2, 7, 4, 6, 8, 5)



Sample input:
4
3 2 4 1


Sample output:
3 1 2 4

Submission status: Accepted

Solution code:
class SegTree:
    def __init__(self, init_val, ide_ele, segfunc):
        self.n = len(init_val)
        self.num =2**(self.n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg = [self.ide_ele]*2*self.num
        self.segfunc = segfunc
        
        #set_val
        for i in range(self.n):
            self.seg[i+self.num-1] = init_val[i]    
        #built
        for i in range(self.num-2,-1,-1) :
            self.seg[i] = segfunc(self.seg[2*i+1], self.seg[2*i+2]) 
    
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    import sys
    input = sys.stdin.readline
    
    N = int(input())
    P = list(map(int,input().split()))
    Even = []
    Odd = []
    D = {}
    for i in range(N//2):
        e = P[2*i]
        o = P[2*i+1]
        D[e] = i
        D[o] = i
        Even.append(e)
        Odd.append(o)
    
    E_Seg = SegTree(Even,float("inf"),min)
    O_Seg = SegTree(Odd,float("inf"),min)
    
    import heapq
    heap = []
    # heapq.heappush(heap, item)
    # heapq.heappop(heap)
    
    def BFS(H):
        L = H[0]
        R = H[1]
        if R <= L:
            return -1,-1,-1,-1,-1
        if L%2==0:
            l = L//2
            r = R//2
            mini = E_Seg.query(l,r+1)
            d_mini = D[mini]
            mini_b = O_Seg.query(d_mini, r+1)
            d_mini_b = D[mini_b]
            
            leftH = (L, 2*d_mini-1)
            centH = (2*d_mini+1, 2*d_mini_b)
            rightH = (2*d_mini_b+2, R)
            return mini, mini_b, leftH, centH, rightH
        else:
            l = L//2
            r = R//2
            mini = O_Seg.query(l, r)
            d_mini = D[mini]
            mini_b = E_Seg.query(d_mini+1, r+1)
            d_mini_b = D[mini_b]
            
            leftH = (L, 2*d_mini)
            centH = (2*d_mini+2, 2*d_mini_b-1)
            rightH = (2*d_mini_b+1, R)
            return mini, mini_b, leftH, centH, rightH
        
    H = (0, N-1)
    m1,m2,LH,CH,RH = BFS(H)
    #print(m1,m2)
    heapq.heappush(heap, [m1,m2,LH,CH,RH])
    Q = []
    while heap != []:
        m1,m2,LH,CH,RH = heapq.heappop(heap)
        Q += [m1,m2]
        
        m1L,m2L,LHL,CHL,RHL = BFS(LH)
        if m1L != -1:
            heapq.heappush(heap, [m1L,m2L,LHL,CHL,RHL])
        
        m1C,m2C,LHC,CHC,RHC = BFS(CH)
        if m1C != -1:
            heapq.heappush(heap, [m1C,m2C,LHC,CHC,RHC])
        
        m1R,m2R,LHR,CHR,RHR = BFS(RH)
        if m1R != -1:
            heapq.heappush(heap, [m1R,m2R,LHR,CHR,RHR])
    print(*Q)
    
    
    
    
main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from heapq import heappush, heappop

N = int(input())
A = [int(x) for x in input().split()]
a_to_i = {a:i for i,a in enumerate(A)}

# sparse table を使ってRMQ
# parityの同じところだけを見るようにしておく

U = len(A).bit_length()
sp = [None,A]
for i in range(2,U):
    L = 1 << (i-1)
    sp.append([x if x < y else y for x,y in zip(sp[-1][:-L], sp[-1][L:])])

def RMQ(x,y):
    # x番目から偶数番目だけ見て[x,y]での最小値を返す
    d = y - x
    if d <= 1:
        return A[x]
    n = d.bit_length()
    arr = sp[n-1]
    ax = arr[x]
    ay = arr[y+2-(1<<(n-1))]
    return ax if ax < ay else ay

def F(x,y):
    # 辞書式で最小の2つ組をとる
    # そのあと、今後調べないといけない区間の一覧を返す
    x1 = RMQ(x,y-1)
    i1 = a_to_i[x1]
    x2 = RMQ(i1+1,y)
    i2 = a_to_i[x2]
    task = ((x,y) for x,y in ((x,i1-1), (i1+1,i2-1), (i2+1,y)) if y > x)
    return x1,x2,task

q = [(None,None,((0,N-1),))]
answer = []
while q:
    x,y,task = heappop(q)
    answer.append(x)
    answer.append(y)
    for left,right in task:
        heappush(q,F(left,right))

print(' '.join(map(str,answer[2:])))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from heapq import heappush, heappop

N = int(input())
A = [int(x) for x in input().split()]
a_to_i = {a:i for i,a in enumerate(A)}

# sparse table を使ってRMQ
# parityの同じところだけを見るようにしておく

U = len(A).bit_length()
sp = [None,A]
for i in range(2,U):
    L = 1 << (i-1)
    sp.append([x if x < y else y for x,y in zip(sp[-1][:-L], sp[-1][L:])])

def RMQ(x,y):
    # x番目から偶数番目だけ見て[x,y]での最小値を返す
    d = y - x
    if d <= 1:
        return A[x]
    n = d.bit_length()
    return min(sp[n-1][x], sp[n-1][y+2-(1<<(n-1))])

def F(x,y):
    # 辞書式で最小の2つ組をとる
    # そのあと、今後調べないといけない区間の一覧を返す
    x1 = RMQ(x,y-1)
    i1 = a_to_i[x1]
    x2 = RMQ(i1+1,y)
    i2 = a_to_i[x2]
    task = ((x,y) for x,y in ((x,i1-1), (i1+1,i2-1), (i2+1,y)) if y > x)
    return x1,x2,task

q = [(None,None,((0,N-1),))]
answer = []
while q:
    x,y,task = heappop(q)
    answer.append(x)
    answer.append(y)
    for left,right in task:
        heappush(q,F(left,right))

print(' '.join(map(str,answer[2:])))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
from heapq import heappush, heappop

N = int(input())
A = np.array(input().split(), dtype=np.int32)
a_to_i = {a:i for i,a in enumerate(A)}

# sparse table を使ってRMQ
# parityの同じところだけを見るようにしておく

U = len(A).bit_length()
sp = [None,A]
for i in range(2,U):
    L = 1 << (i-1)
    sp.append(np.minimum(sp[-1][:-L], sp[-1][L:]))

def RMQ(x,y):
    # x番目から偶数番目だけ見て[x,y]での最小値を返す
    d = y - x
    if d <= 1:
        return A[x]
    n = d.bit_length()
    return min(sp[n-1][x], sp[n-1][y+2-(1<<(n-1))])

def F(x,y):
    # 辞書式で最小の2つ組をとる
    # そのあと、今後調べないといけない区間の一覧を返す
    x1 = RMQ(x,y-1)
    i1 = a_to_i[x1]
    x2 = RMQ(i1+1,y)
    i2 = a_to_i[x2]
    task = ((x,y) for x,y in ((x,i1-1), (i1+1,i2-1), (i2+1,y)) if y > x)
    return x1,x2,task

q = [(None,None,((0,N-1),))]
answer = []
while q:
    x,y,task = heappop(q)
    answer.append(x)
    answer.append(y)
    for left,right in task:
        heappush(q,F(left,right))

print(' '.join(map(str,answer[2:])))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
from heapq import heappush, heappop

N = int(input())
A = np.array(input().split(), dtype=np.int32)
a_to_i = {a:i for i,a in enumerate(A)}

# sparse table を使ってRMQ
# parityの同じところだけを見るようにしておく

U = len(A).bit_length()
sp = [None,A]
for i in range(2,U):
    L = 1 << (i-1)
    sp.append(np.minimum(sp[-1][:-L], sp[-1][L:]))

def RMQ(x,y):
    if (y-x)&1: 
        y -= 1
    # x番目から偶数番目だけ見て[x,y]での最小値を返す
    d = y - x
    if d <= 1:
        return A[x]
    n = d.bit_length()
    return min(sp[n-1][x], sp[n-1][y+2-(1<<(n-1))])

def F(x,y):
    # 辞書式で最小の2つ組をとる
    # そのあと、今後調べないといけない区間の一覧を返す
    x1 = RMQ(x,y)
    i1 = a_to_i[x1]
    x2 = RMQ(i1+1,y)
    i2 = a_to_i[x2]
    task = ((x,y) for x,y in ((x,i1-1), (i1+1,i2-1), (i2+1,y)) if y > x)
    return x1,x2,task

q = [(None,None,((0,N-1),))]
answer = []
while q:
    x,y,task = heappop(q)
    if x != None:
        answer.append(x)
        answer.append(y)
    for left,right in task:
        heappush(q,F(left,right))

print(' '.join(map(str,answer)))

Submission status: Accepted

Solution code:
# seishin.py
N = int(input())
*P, = map(int, input().split())
M = [0]*(N+1)
for i, p in enumerate(P):
    M[p] = i

INF = 10**9
def init(P, n):
    n0 = 2 ** (n-1).bit_length()
    data = [INF]*(n0*2)
    data[n0-1:n0+n-1] = P
    for i in range(n0-2, -1, -1):
        data[i] = min(data[2*i+1], data[2*i+2])
    return data

def get_data(data, l, r):
    n0 = len(data)//2
    l += n0
    r += n0
    while l < r:
        if r&1:
            r -= 1
            yield data[r-1]
        if l&1:
            yield data[l-1]
            l += 1
        l >>= 1
        r >>= 1

def get(data, l, r):
    return min(get_data(data, l, r))

d0 = init(P[0::2], N//2)
d1 = init(P[1::2], N//2)

def query_x(l, r):
    if l % 2 == 0:
        x = get(d0, l//2, r//2)
    else:
        x = get(d1, l//2, r//2)
    return x
def query_y(l, r):
    if l % 2 == 0:
        y = get(d1, l//2, r//2)
    else:
        y = get(d0, (l+1)//2, (r+1)//2)
    return y

from heapq import heappush, heappop
que = [(query_x(0, N), 0, N)]
ans = []
while que:
    x, l, r = heappop(que)
    if l+2 < r:
        xi = M[x]
        y = query_y(xi, r)

        yi = M[y]

        # [l, xi)
        if l < xi:
            heappush(que, (query_x(l, xi), l, xi))
        # [xi+1, yi)
        if xi+1 < yi:
            heappush(que, (query_x(xi+1, yi), xi+1, yi))
        # [yi+1, r)
        if yi+1 < r:
            heappush(que, (query_x(yi+1, r), yi+1, r))
    else:
        y = P[r-1]

    ans.append("%d %d" % (x, y))
print(*ans)

Submission status: Accepted

Solution code:
# seishin.py
N = int(input())
*P, = map(int, input().split())
M = [0]*(N+1)
for i, p in enumerate(P):
    M[p] = i

INF = 10**9
def init(P, n):
    n0 = 2 ** (n-1).bit_length()
    data = [INF]*(n0*2)
    data[n0-1:n0+n-1] = P
    for i in range(n0-2, -1, -1):
        data[i] = min(data[2*i+1], data[2*i+2])
    return data

"""
def __get(data, a, b, k, l, r):
    if a <= l and r <= b:
        return data[k]
    if b <= l or r <= a:
        return INF
    vl = __get(data, a, b, 2*k+1, l, (l+r)//2)
    vr = __get(data, a, b, 2*k+2, (l+r)//2, r)
    return min(vl, vr)
"""

def get_data(data, l, r):
    n0 = len(data)//2
    l += n0
    r += n0
    while l < r:
        if r&1:
            r -= 1
            yield data[r-1]
        if l&1:
            yield data[l-1]
            l += 1
        l >>= 1
        r >>= 1
    yield INF

def get(data, l, r):
    #return __get(data, l, r, 0, 0, len(data)//2)
    return min(get_data(data, l, r))

d0 = init(P[0::2], N//2)
d1 = init(P[1::2], N//2)

def query_x(l, r):
    if l % 2 == 0:
        x = get(d0, l//2, r//2)
    else:
        x = get(d1, l//2, r//2)
    return x
def query_y(l, r):
    if l % 2 == 0:
        y = get(d1, l//2, r//2)
    else:
        y = get(d0, (l+1)//2, (r+1)//2)
    return y

from heapq import heappush, heappop
que = [(query_x(0, N), 0, N)]
ans = []
while que:
    x, l, r = heappop(que)
    if l+2 < r:
        xi = M[x]
        y = query_y(xi, r)

        yi = M[y]

        # [l, xi)
        if l < xi:
            heappush(que, (query_x(l, xi), l, xi))
        # [xi+1, yi)
        if xi+1 < yi:
            heappush(que, (query_x(xi+1, yi), xi+1, yi))
        # [yi+1, r)
        if yi+1 < r:
            heappush(que, (query_x(yi+1, r), yi+1, r))
    else:
        y = P[r-1]

    ans.append("%d %d" % (x, y))
print(*ans)

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
import heapq
import sys
input=sys.stdin.readline

class SegmentTreeMin():
  def __init__(self,n,init):
    self.offset=2**((n-1).bit_length())
    self.tree=[init]*(2*self.offset)
    self.init=init
  def update(self,pos,val):
    pos+=self.offset
    self.tree[pos]=val
    while pos>1:
      pos=pos//2
      self.tree[pos]=min(self.tree[2*pos],self.tree[2*pos+1])
  def query(self,l,r):
    l+=self.offset
    r+=self.offset
    ret=self.init
    while l<=r:
      ret=min(ret,self.tree[r])
      r=(r-1)//2
      ret=min(ret,self.tree[l])
      l=(l+1)//2
    return ret

n=int(input())
arr=list(map(int,input().split()))
odds=SegmentTreeMin(n//2,10**18)
evens=SegmentTreeMin(n//2,10**18)
dic={}
for i in range(n):
  dic[arr[i]]=i
  if i%2==0:
    odds.update(i//2,arr[i])
  else:
    evens.update(i//2,arr[i])
q=[]
heapq.heappush(q,(odds.query(0,n//2-1),0,n-1))
ans=[]
while len(q)!=0:
  _,l,r=heapq.heappop(q)
  if l%2==0:
    a=odds.query(l//2,r//2)
    odds.update(dic[a]//2,10**18)
    b=evens.query(dic[a]//2,r//2)
    evens.update(dic[b]//2,10**18)
    ans.append(a)
    ans.append(b)
    tl=dic[a]
    tr=dic[b]
    if (tl-1)-l>0:
      heapq.heappush(q,(odds.query(l,(tl-1)//2),l,tl-1))
    if (tr-1)-(tl+1)>0:
      heapq.heappush(q,(evens.query((tl+1)//2,(tr-1)//2),tl+1,tr-1))
    if r-(tr+1)>0:
      heapq.heappush(q,(odds.query((tr+1)//2,r//2),tr+1,r))
  else:
    a=evens.query(l//2,r//2)
    evens.update(dic[a]//2,10**18)
    b=odds.query(dic[a]//2,r//2)
    odds.update(dic[b]//2,10**18)
    ans.append(a)
    ans.append(b)
    tl=dic[a]
    tr=dic[b]
    if (tl-1)-l>0:
      heapq.heappush(q,(evens.query(l,(tl-1)//2),l,tl-1))
    if (tr-1)-(tl+1)>0:
      heapq.heappush(q,(odds.query((tl+1)//2,(tr-1)//2),tl+1,tr-1))
    if r-(tr+1)>0:
      heapq.heappush(q,(evens.query((tr+1)//2,r//2),tr+1,r))
print(*ans)

Submission status: Runtime Error

Solution code:
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()

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()
#define dump(x) cerr << #x << " = " << (x) << endl
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

template<class T, class U> void chmin(T& t, const U& u) { if (t > u) t = u; }
template<class T, class U> void chmax(T& t, const U& u) { if (t < u) t = u; }

template<class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	os<<"{";
	rep(i, v.size()) {
		if (i) os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

const int SZ = 1 << 18;
const int INF = TEN(9);

struct segtree {
	vector<pii> dat;

	const pii inf = mp(INF, INF);

	void init() {
		dat.resize(SZ * 2);
		rep(i, SZ * 2) dat[i] = inf;
	}

	void update(int pos, int x) {
		dat[pos + SZ - 1] = mp(x, pos);
		pos += SZ - 1;

		while (pos > 0) {
			pos = (pos - 1) / 2;
			dat[pos] = min(dat[pos * 2 + 1], dat[pos * 2 + 2]);
		}
	}

	pii get(int a, int b, int k = 0, int l = 0, int r = SZ) {
		if (b <= l || r <= a) return inf;
		if (a <= l && r <= b) return dat[k];
		return min(get(a, b, k * 2 + 1, l, (l + r) / 2), get(a, b, k * 2 + 2, (l + r) / 2, r));
	}
} seg[2];

int main() {
	seg[0].init();
	seg[1].init();

	int N; cin >> N;
	V<int> p(N);

	rep(i, N) {
		cin >> p[i];
		seg[i % 2].update(i, p[i]);
	}

	using Data = pair<pii, pii>;
	priority_queue<Data, vector<Data>, greater<Data>> que;

	auto add = [&](int l, int r) {
		auto p = seg[l%2].get(l, r);
		if (l >= r || p.fi == INF) return ;
		que.push(mp(seg[l%2].get(l, r), mp(l, r)));
	};

	add(0, N);
	V<int> ans;

	while (!que.empty()) {
		auto p = que.top(); que.pop();
		int val = p.fi.fi, pos = p.fi.se; 
		int l = p.se.fi, r = p.se.se;

		auto nx = seg[1-l%2].get(pos + 1, r);

		ans.pb(val);
		ans.pb(nx.fi);
		add(l, pos);
		add(pos + 1, nx.se);
		add(nx.se + 1, r);
	}

	rep(i, N) printf("%d%c", ans[i], i == N - 1 ? '\n' : ' ');
 
	return 0;
}

Submission status: Runtime Error

Solution code:
class SegmentTree:#抽象セグ木
    def __init__(self, N, id, fun):#id:単位元
        self.N0 = 2**(N-1).bit_length()
        self.id = id
        self.data = [(self.id, -1)]*(2*self.N0)
        self.fun = fun
    def update(self, i, x):
        k=i+self.N0-1
        self.data[k] = (x, i)
        while k>=0:
            k = (k-1)//2
            self.data[k] = self.fun(self.data[2*k+1], self.data[2*k+2])
    def query(self, l, r):#[l, r)
        L = l+self.N0; R = r+self.N0
        s = (self.id, -1)
        while L<R:
            if R&1:
                R-=1
                s = self.fun(s, self.data[R-1])
            if L&1:
                s = self.fun(s, self.data[L-1])
                L+=1
            L >>= 1; R>>=1
        return s
import sys
input = sys.stdin.readline
print = sys.stdin.write
inf = 10**18
N = int(input())
p = list(map(int, input().split()))
S1 = SegmentTree(N//2, inf, min)
S2 = SegmentTree(N//2, inf, min)
res = []
def add(l, r):
    if l%2 == 0:
        x, i = S1.query(l//2, r//2)
        i = i*2
    else:
        x, i = S2.query(l//2, r//2)
        i = i*2+1
    heappush(que, (x, i, l, r))

from heapq import heappop, heappush
for i, x in enumerate(p[::2]):
    S1.update(i, x)
for i, x in enumerate(p[1::2]):
    S2.update(i, x)
x, i = S1.query(0, N//2)
que = [(x, i*2, 0, N)]
while que:
    x, i, l, r = heappop(que)
    if r-l==2:
        res.append(p[l])
        res.append(p[l+1])
        continue
    if r-l<2:
        continue
    if l%2 == 0:
        y, j = S2.query(i//2, r//2)
        j = j*2+1
    else:
        y, j = S1.query(i//2+1, r//2+1)
        j = j*2
    res.append(x)
    res.append(y)
    add(l, i)
    add(i+1, j)
    add(j+1, r)
print(*res)

Submission status: Runtime Error

Solution code:
class SegmentTree:#抽象セグ木
    def __init__(self, N, id, fun):#id:単位元
        self.N0 = 2**(N-1).bit_length()
        self.id = id
        self.data = [(self.id, i) for i in range(2*self.N0)]
        self.fun = fun
    def update(self, k, x):
        k+=self.N0-1
        self.data[k] = (x, k-self.N0+1)
        while k>=0:
            k = (k-1)//2
            self.data[k] = self.fun(self.data[2*k+1], self.data[2*k+2])
    def query(self, l, r):#[l, r)
        L = l+self.N0; R = r+self.N0
        s = (self.id, self.id)
        while L<R:
            if R&1:
                R-=1
                s = self.fun(s, self.data[R-1])
            if L&1:
                s = self.fun(s, self.data[L-1])
                L+=1
            L >>= 1; R>>=1
        return s
inf = 10**10
N = int(input())
p = list(map(int, input().split()))
S1 = SegmentTree(N//2, inf, min)
S2 = SegmentTree(N//2, inf, min)
que = [(0, 0, N)]
res = []
for i, x in enumerate(p[::2]):
    S1.update(i, x)
for i, x in enumerate(p[1::2]):
    S2.update(i, x)
while que:
    k, l, r = que.pop()
    if l>=r:
        continue
    if r-l == 2:
        res.append((k+1, p[l], p[l+1]))
        continue
    if l%2 == 0:
        x, i = S1.query(l//2, r//2)
        i*=2
        que.append((k+1, l, i))
        y, j = S2.query(i//2, r//2)
        j = j*2+1
        res.append((k+1, x, y))
        que.append((k+1, i+1, j))
        que.append((k+1, j+1, r))
    else:
        x, i = S2.query(l//2, r//2)
        i*=2+1
        que.append((k+1, l, i))
        y, j = S1.query(i//2+1, r//2+1)
        j = j*2
        res.append((k+1, x, y))
        que.append((k+1, i+1, j))
        que.append((k+1, j+1, r))
res.sort()
ans = []
for a, b, c in res:
    ans.append(b)
    ans.append(c)
print(*ans)

Submission status: Runtime Error

Solution code:
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()