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: Time Limit Exceeded

Solution code:
"""

https://atcoder.jp/contests/arc080/tasks/arc080_c

まず、辞書順最小なので一番左にできる要素はどれか考える

ABCD
→可能なのは A,C

→偶数番目だけ？(0 indexedで)
→右に奇数個・左に偶数個ある場合しか先頭にはなれないので正しそう

次に、2番目になる要素はどれか？
→一番目より左は確定
→奇数個並んでる場合、最後に残せるやつ
ABCDEだと
→A,C,E なので奇数番目だけ

3番目の要素は？
→偶数番目から自由に選べる
4番目は？
→最後に選んだ偶数番目から右に探索して、探索済みが出てくるまでに当たる奇数番目のうち最小

あとは高速化だ！

分割統治
偶奇分けて最小と最大2つのRMQを出せるようにしとく
→めんどすぎ！！！

偶数番目と奇数番目・最小で2つのセグ木
偶数番目から最小を選ぶ(X)
→それより右の奇数番目から最小を選ぶ(Y)
その左側、真ん中、右側を分けておなじことをする

(X,Y),3つの部分を小さいほうからどん欲にとってマージした奴
をreturnする

SPTを使えば早いか
maxは-1をかけて出せばいいや

======ちょっと答えを見た======

マージ部分がやばい？
親が選択されるまで子は選択できない
優先度付きキューで管理か
親を処理した時点で子を優先度付きキューに入れるのか

(左値,右値,左index,右index,L,R)を入れればいいか

"""
from sys import stdin
import sys
import heapq

def make_ST(n,first): #firstで初期化された、葉がn要素を超えるように2のべき乗個用意されたリストを返す

    i = 0
    ret = []
    while 2 ** (i-1) < n:

        for j in range(2 ** i):
            ret.append(first)

        i += 1

    return ret

def RMQ_update_point(num,point,tree): #葉のindex(0-origin)がpointの要素をnumにする/treeはセグ木

    i = (len(tree) - 1) // 2 + point
    tree[i] = num
    while i > 0:
        i = (i - 1) // 2
        tree[i] = min(tree[i * 2 + 2] , tree[i * 2 + 1])

    return

def RMQ_query(a,b,k,l,r,tree): #query区間左,右,注目ノード番号,担当範囲左,担当範囲右,木

    if r <= a or b <= l: #区間が完全にかぶらない場合inf
        return (float("inf"),float("inf"))
    
    if a <= l and r <= b: #区間が完全に含まれる場合自分
        return tree[k]

    c1 = RMQ_query(a,b,2*k+1,l,(l+r)//2,tree)
    c2 = RMQ_query(a,b,2*k+2,(l+r)//2,r,tree)   

    return min(c1,c2)
        

def want(L,R):

    if L >= R:
        return
    elif L + 1 == R:
        heapq.heappush( q, (p[L],p[R],float("inf"),float("-inf"),float("inf"),float("-inf")) )
        return

    if L % 2 == 0:
        nx,xind = RMQ_query(L,R+1,0,0,(len(emin)+1)//2,emin)
        ny,yind = RMQ_query(xind+1,R+1,0,0,(len(omin)+1)//2,omin)
    else:
        nx,xind = RMQ_query(L,R+1,0,0,(len(omin)+1)//2,omin)
        ny,yind = RMQ_query(xind+1,R+1,0,0,(len(emin)+1)//2,emin)

    #print (L,R,xind,yind)

    heapq.heappush( q , (nx,ny,xind,yind,L,R) )
    return

N = int(stdin.readline())
p = list(map(int, stdin.readline().split()))


omin = make_ST(N, (float("inf") , float("inf")) )
emin = make_ST(N, (float("inf") , float("inf")) )

for i in range(N):
    if i % 2 == 0:
        RMQ_update_point( (p[i],i) ,i,emin)
    else:
        RMQ_update_point( (p[i],i) ,i,omin)

q = []
want(0,N-1)
ans = []

while len(q) > 0:

    x,y,xi,yi,NL,NR = heapq.heappop(q)
    ans.append(x)
    ans.append(y)

    want(NL,xi-1)
    want(xi+1,yi-1)
    want(yi+1,NR)

print (*ans)

Submission status: Time Limit Exceeded

Solution code:
"""

https://atcoder.jp/contests/arc080/tasks/arc080_c

まず、辞書順最小なので一番左にできる要素はどれか考える

ABCD
→可能なのは A,C

→偶数番目だけ？(0 indexedで)
→右に奇数個・左に偶数個ある場合しか先頭にはなれないので正しそう

次に、2番目になる要素はどれか？
→一番目より左は確定
→奇数個並んでる場合、最後に残せるやつ
ABCDEだと
→A,C,E なので奇数番目だけ

3番目の要素は？
→偶数番目から自由に選べる
4番目は？
→最後に選んだ偶数番目から右に探索して、探索済みが出てくるまでに当たる奇数番目のうち最小

あとは高速化だ！

分割統治
偶奇分けて最小と最大2つのRMQを出せるようにしとく
→めんどすぎ！！！

偶数番目と奇数番目・最小で2つのセグ木
偶数番目から最小を選ぶ(X)
→それより右の奇数番目から最小を選ぶ(Y)
その左側、真ん中、右側を分けておなじことをする

(X,Y),3つの部分を小さいほうからどん欲にとってマージした奴
をreturnする

SPTを使えば早いか
maxは-1をかけて出せばいいや

======ちょっと答えを見た======

マージ部分がやばい？
親が選択されるまで子は選択できない
優先度付きキューで管理か
親を処理した時点で子を優先度付きキューに入れるのか

(左値,右値,左index,右index,L,R)を入れればいいか

"""
from sys import stdin
import sys
import heapq

def make_ST(n,first): #firstで初期化された、葉がn要素を超えるように2のべき乗個用意されたリストを返す

    i = 0
    ret = []
    while 2 ** (i-1) < n:

        for j in range(2 ** i):
            ret.append(first)

        i += 1

    return ret

def RMQ_update_point(num,point,tree): #葉のindex(0-origin)がpointの要素をnumにする/treeはセグ木

    i = (len(tree) - 1) // 2 + point
    tree[i] = num
    while i > 0:
        i = (i - 1) // 2
        tree[i] = min(tree[i * 2 + 2] , tree[i * 2 + 1])

    return

def RMQ_query(a,b,k,l,r,tree): #query区間左,右,注目ノード番号,担当範囲左,担当範囲右,木

    if r <= a or b <= l: #区間が完全にかぶらない場合inf
        return (float("inf"),float("inf"))
    
    if a <= l and r <= b: #区間が完全に含まれる場合自分
        return tree[k]

    c1 = RMQ_query(a,b,2*k+1,l,(l+r)//2,tree)
    c2 = RMQ_query(a,b,2*k+2,(l+r)//2,r,tree)   

    return min(c1,c2)
        

def want(L,R):

    if L >= R:
        return
    elif L + 1 == R:
        heapq.heappush( q, (p[L],p[R],float("inf"),float("-inf"),float("inf"),float("-inf")) )
        return

    if L % 2 == 0:
        nx,xind = RMQ_query(L,R+1,0,0,(len(emin)+1)//2,emin)
        ny,yind = RMQ_query(xind+1,R+1,0,0,(len(omin)+1)//2,omin)
    else:
        nx,xind = RMQ_query(L,R+1,0,0,(len(omin)+1)//2,omin)
        ny,yind = RMQ_query(xind+1,R+1,0,0,(len(emin)+1)//2,emin)

    #print (L,R,xind,yind)

    heapq.heappush( q , (nx,ny,xind,yind,L,R) )
    return

N = int(input())
p = list(map(int, stdin.readline().split()))


omin = make_ST(N, (float("inf") , float("inf")) )
emin = make_ST(N, (float("inf") , float("inf")) )

for i in range(N):
    if i % 2 == 0:
        RMQ_update_point( (p[i],i) ,i,emin)
    else:
        RMQ_update_point( (p[i],i) ,i,omin)

q = []
want(0,N-1)
ans = []

while len(q) > 0:

    x,y,xi,yi,NL,NR = heapq.heappop(q)
    ans.append(x)
    ans.append(y)

    want(NL,xi-1)
    want(xi+1,yi-1)
    want(yi+1,NR)

print (*ans)

Submission status: Time Limit Exceeded

Solution code:

"""

https://atcoder.jp/contests/arc080/tasks/arc080_c

まず、辞書順最小なので一番左にできる要素はどれか考える

ABCD
→可能なのは A,C

→偶数番目だけ？(0 indexedで)
→右に奇数個・左に偶数個ある場合しか先頭にはなれないので正しそう

次に、2番目になる要素はどれか？
→一番目より左は確定
→奇数個並んでる場合、最後に残せるやつ
ABCDEだと
→A,C,E なので奇数番目だけ

3番目の要素は？
→偶数番目から自由に選べる
4番目は？
→最後に選んだ偶数番目から右に探索して、探索済みが出てくるまでに当たる奇数番目のうち最小

あとは高速化だ！

分割統治
偶奇分けて最小と最大2つのRMQを出せるようにしとく
→めんどすぎ！！！

偶数番目と奇数番目・最小で2つのセグ木
偶数番目から最小を選ぶ(X)
→それより右の奇数番目から最小を選ぶ(Y)
その左側、真ん中、右側を分けておなじことをする

(X,Y),3つの部分を小さいほうからどん欲にとってマージした奴
をreturnする

SPTを使えば早いか
maxは-1をかけて出せばいいや

======ちょっと答えを見た======

マージ部分がやばい？
親が選択されるまで子は選択できない
優先度付きキューで管理か
親を処理した時点で子を優先度付きキューに入れるのか

(左値,右値,左index,右index,L,R)を入れればいいか

"""

import sys
import heapq

def make_ST(n,first): #firstで初期化された、葉がn要素を超えるように2のべき乗個用意されたリストを返す

    i = 0
    ret = []
    while 2 ** (i-1) < n:

        for j in range(2 ** i):
            ret.append(first)

        i += 1

    return ret

def RMQ_update_point(num,point,tree): #葉のindex(0-origin)がpointの要素をnumにする/treeはセグ木

    i = (len(tree) - 1) // 2 + point
    tree[i] = num
    while i > 0:
        i = (i - 1) // 2
        tree[i] = min(tree[i * 2 + 2] , tree[i * 2 + 1])

    return

def RMQ_query(a,b,k,l,r,tree): #query区間左,右,注目ノード番号,担当範囲左,担当範囲右,木

    if r <= a or b <= l: #区間が完全にかぶらない場合inf
        return (float("inf"),float("inf"))
    
    if a <= l and r <= b: #区間が完全に含まれる場合自分
        return tree[k]

    c1 = RMQ_query(a,b,2*k+1,l,(l+r)//2,tree)
    c2 = RMQ_query(a,b,2*k+2,(l+r)//2,r,tree)   

    return min(c1,c2)
        

def want(L,R):

    if L >= R:
        return

    if L % 2 == 0:
        nx,xind = RMQ_query(L,R+1,0,0,(len(emin)+1)//2,emin)
        ny,yind = RMQ_query(xind+1,R+1,0,0,(len(omin)+1)//2,omin)
    else:
        nx,xind = RMQ_query(L,R+1,0,0,(len(omin)+1)//2,omin)
        ny,yind = RMQ_query(xind+1,R+1,0,0,(len(emin)+1)//2,emin)

    #print (L,R,xind,yind)

    heapq.heappush( q , (nx,ny,xind,yind,L,R) )
    return

N = int(input())
p = list(map(int,input().split()))


omin = make_ST(N, (float("inf") , float("inf")) )
emin = make_ST(N, (float("inf") , float("inf")) )

for i in range(N):
    if i % 2 == 0:
        RMQ_update_point( (p[i],i) ,i,emin)
    else:
        RMQ_update_point( (p[i],i) ,i,omin)

q = []
want(0,N-1)
ans = [0]*N
ind=0

for i in range(N//2):

    x,y,xi,yi,NL,NR = heapq.heappop(q)
    ans[ind] = x
    ans[ind+1] = y
    ind += 2

    want(NL,xi-1)
    want(xi+1,yi-1)
    want(yi+1,NR)

print (*ans)

Submission status: Time Limit Exceeded

Solution code:

"""

https://atcoder.jp/contests/arc080/tasks/arc080_c

まず、辞書順最小なので一番左にできる要素はどれか考える

ABCD
→可能なのは A,C

→偶数番目だけ？(0 indexedで)
→右に奇数個・左に偶数個ある場合しか先頭にはなれないので正しそう

次に、2番目になる要素はどれか？
→一番目より左は確定
→奇数個並んでる場合、最後に残せるやつ
ABCDEだと
→A,C,E なので奇数番目だけ

3番目の要素は？
→偶数番目から自由に選べる
4番目は？
→最後に選んだ偶数番目から右に探索して、探索済みが出てくるまでに当たる奇数番目のうち最小

あとは高速化だ！

分割統治
偶奇分けて最小と最大2つのRMQを出せるようにしとく
→めんどすぎ！！！

偶数番目と奇数番目・最小で2つのセグ木
偶数番目から最小を選ぶ(X)
→それより右の奇数番目から最小を選ぶ(Y)
その左側、真ん中、右側を分けておなじことをする

(X,Y),3つの部分を小さいほうからどん欲にとってマージした奴
をreturnする

SPTを使えば早いか
maxは-1をかけて出せばいいや

======ちょっと答えを見た======

マージ部分がやばい？
親が選択されるまで子は選択できない
優先度付きキューで管理か
親を処理した時点で子を優先度付きキューに入れるのか

(左値,右値,左index,右index,L,R)を入れればいいか

"""

import sys
import heapq

def make_ST(n,first): #firstで初期化された、葉がn要素を超えるように2のべき乗個用意されたリストを返す

    i = 0
    ret = []
    while 2 ** (i-1) < n:

        for j in range(2 ** i):
            ret.append(first)

        i += 1

    return ret

def RMQ_update_point(num,point,tree): #葉のindex(0-origin)がpointの要素をnumにする/treeはセグ木

    i = (len(tree) - 1) // 2 + point
    tree[i] = num
    while i > 0:
        i = (i - 1) // 2
        tree[i] = min(tree[i * 2 + 2] , tree[i * 2 + 1])

    return

def RMQ_query(a,b,k,l,r,tree): #query区間左,右,注目ノード番号,担当範囲左,担当範囲右,木

    if r <= a or b <= l: #区間が完全にかぶらない場合inf
        return (float("inf"),float("inf"))
    
    if a <= l and r <= b: #区間が完全に含まれる場合自分
        return tree[k]

    c1 = RMQ_query(a,b,2*k+1,l,(l+r)//2,tree)
    c2 = RMQ_query(a,b,2*k+2,(l+r)//2,r,tree)   

    return min(c1,c2)
        

def want(L,R):

    if L >= R:
        return
    elif L + 1 == R:
        heapq.heappush( q, (p[L],p[R],float("inf"),float("-inf"),float("inf"),float("-inf")) )
        return

    if L % 2 == 0:
        nx,xind = RMQ_query(L,R+1,0,0,(len(emin)+1)//2,emin)
        ny,yind = RMQ_query(xind+1,R+1,0,0,(len(omin)+1)//2,omin)
    else:
        nx,xind = RMQ_query(L,R+1,0,0,(len(omin)+1)//2,omin)
        ny,yind = RMQ_query(xind+1,R+1,0,0,(len(emin)+1)//2,emin)

    #print (L,R,xind,yind)

    heapq.heappush( q , (nx,ny,xind,yind,L,R) )
    return

N = int(input())
p = list(map(int,input().split()))


omin = make_ST(N, (float("inf") , float("inf")) )
emin = make_ST(N, (float("inf") , float("inf")) )

for i in range(N):
    if i % 2 == 0:
        RMQ_update_point( (p[i],i) ,i,emin)
    else:
        RMQ_update_point( (p[i],i) ,i,omin)

q = []
want(0,N-1)
ans = []

while len(q) > 0:

    x,y,xi,yi,NL,NR = heapq.heappop(q)
    ans.append(x)
    ans.append(y)

    want(NL,xi-1)
    want(xi+1,yi-1)
    want(yi+1,NR)

print (*ans)

Submission status: Time Limit Exceeded

Solution code:

"""

https://atcoder.jp/contests/arc080/tasks/arc080_c

まず、辞書順最小なので一番左にできる要素はどれか考える

ABCD
→可能なのは A,C

→偶数番目だけ？(0 indexedで)
→右に奇数個・左に偶数個ある場合しか先頭にはなれないので正しそう

次に、2番目になる要素はどれか？
→一番目より左は確定
→奇数個並んでる場合、最後に残せるやつ
ABCDEだと
→A,C,E なので奇数番目だけ

3番目の要素は？
→偶数番目から自由に選べる
4番目は？
→最後に選んだ偶数番目から右に探索して、探索済みが出てくるまでに当たる奇数番目のうち最小

あとは高速化だ！

分割統治
偶奇分けて最小と最大2つのRMQを出せるようにしとく
→めんどすぎ！！！

偶数番目と奇数番目・最小で2つのセグ木
偶数番目から最小を選ぶ(X)
→それより右の奇数番目から最小を選ぶ(Y)
その左側、真ん中、右側を分けておなじことをする

(X,Y),3つの部分を小さいほうからどん欲にとってマージした奴
をreturnする

SPTを使えば早いか
maxは-1をかけて出せばいいや

======ちょっと答えを見た======

マージ部分がやばい？
親が選択されるまで子は選択できない
優先度付きキューで管理か
親を処理した時点で子を優先度付きキューに入れるのか

(左値,右値,左index,右index,L,R)を入れればいいか

"""

import sys
import heapq
sys.setrecursionlimit(200001)

#RMQ用のSparseTableを作成
import math
def make_SparseTable(lis):

    spt_len = 0
    while spt_len ** 2 <= len(lis):
        spt_len += 1
    spt_len += 5

    N = len(lis)
    ret = [[float("inf")] * spt_len for i in range(N)]

    for i in range(N):
        ret[i][0] = lis[i]
    
    for j in range(spt_len-1):
        j += 1

        for i in range(N):

            if i + 2**(j-1) < N:
                ret[i][j] = min(ret[i][j-1] , ret[i+2**(j-1)][j-1])
            else:
                ret[i][j] = ret[i][j-1]

    return ret

#[a,b]の最小値を求める
def RMQ_SPT(a,b,spt):

    
    if a == b:
        return (p[a],a)
    
    qlen = b-a+1
    ind = int(math.log(qlen,2))

    #print (a,b,ind,b-2**ind+1)

    return min(spt[a][ind] , spt[b-2**ind+1][ind])

def want(L,R):

    if L >= R:
        return
    elif L + 1 == R:
        heapq.heappush( q, (p[L],p[R],float("inf"),float("-inf"),float("inf"),float("-inf")) )
        return

    if L % 2 == 0:
        nx,xind = RMQ_SPT(L,R,emin)
        ny,yind = RMQ_SPT(xind+1,R,omin)
    else:
        nx,xind = RMQ_SPT(L,R,omin)
        ny,yind = RMQ_SPT(xind+1,R,emin)

    #print (L,R,xind,yind)

    heapq.heappush( q , (nx,ny,xind,yind,L,R) )
    return

N = int(input())
p = list(map(int,input().split()))


ominL = []
eminL = []
for i in range(N):
    if i % 2 == 0:
        ominL.append( (float("inf"),i) )
        eminL.append( ( p[i] , i ) )
    else:
        eminL.append( (float("inf"),i) )
        ominL.append( ( p[i] , i ) )

emin = make_SparseTable(eminL)
omin = make_SparseTable(ominL)

q = []
want(0,N-1)
ans = []

while len(q) > 0:

    x,y,xi,yi,NL,NR = heapq.heappop(q)
    ans.append(x)
    ans.append(y)

    want(NL,xi-1)
    want(xi+1,yi-1)
    want(yi+1,NR)

print (*ans)

Submission status: Time Limit Exceeded

Solution code:

"""

https://atcoder.jp/contests/arc080/tasks/arc080_c

まず、辞書順最小なので一番左にできる要素はどれか考える

ABCD
→可能なのは A,C

→偶数番目だけ？(0 indexedで)
→右に奇数個・左に偶数個ある場合しか先頭にはなれないので正しそう

次に、2番目になる要素はどれか？
→一番目より左は確定
→奇数個並んでる場合、最後に残せるやつ
ABCDEだと
→A,C,E なので奇数番目だけ

3番目の要素は？
→偶数番目から自由に選べる
4番目は？
→最後に選んだ偶数番目から右に探索して、探索済みが出てくるまでに当たる奇数番目のうち最小

あとは高速化だ！

分割統治
偶奇分けて最小と最大2つのRMQを出せるようにしとく
→めんどすぎ！！！

偶数番目と奇数番目・最小で2つのセグ木
偶数番目から最小を選ぶ(X)
→それより右の奇数番目から最小を選ぶ(Y)
その左側、真ん中、右側を分けておなじことをする

(X,Y),3つの部分を小さいほうからどん欲にとってマージした奴
をreturnする

SPTを使えば早いか
maxは-1をかけて出せばいいや

"""

import sys
sys.setrecursionlimit(200001)

#RMQ用のSparseTableを作成
import math
def make_SparseTable(lis):

    spt_len = 0
    while spt_len ** 2 <= len(lis):
        spt_len += 1
    spt_len += 5

    N = len(lis)
    ret = [[float("inf")] * spt_len for i in range(N)]

    for i in range(N):
        ret[i][0] = lis[i]
    
    for j in range(spt_len-1):
        j += 1

        for i in range(N):

            if i + 2**(j-1) < N:
                ret[i][j] = min(ret[i][j-1] , ret[i+2**(j-1)][j-1])
            else:
                ret[i][j] = ret[i][j-1]

    return ret

#[a,b]の最小値を求める
def RMQ_SPT(a,b,spt):

    
    if a == b:
        return (p[a],a)
    
    qlen = b-a+1
    ind = int(math.log(qlen,2))

    #print (a,b,ind,b-2**ind+1)

    return min(spt[a][ind] , spt[b-2**ind+1][ind])

def want(L,R):

    if L >= R:
        return [(float("inf"),float("inf"))]
    elif L + 1 == R:
        return [(p[L],p[R]),(float("inf"),float("inf"))]

    ret = []
    add = []

    if L % 2 == 0:
        nx,xind = RMQ_SPT(L,R,emin)
        ny,yind = RMQ_SPT(xind+1,R,omin)
        ret.append( (nx,ny) )
    else:
        nx,xind = RMQ_SPT(L,R,omin)
        ny,yind = RMQ_SPT(xind+1,R,emin)
        ret.append( (nx,ny) )

    #print (L,R,xind,yind)

    LL = want(L,xind-1)
    MM = want(xind+1,yind-1)
    RR = want(yind+1,R)
        
    li = 0
    mi = 0
    ri = 0

    for i in range(len(LL)+len(MM)+len(RR)-3):
        nmin = min(LL[li] , MM[mi] , RR[ri])
        if nmin == LL[li]:
            ret.append(LL[li])
            li += 1
        elif nmin == MM[mi]:
            ret.append(MM[mi])
            mi += 1
        else:
            ret.append(RR[ri])
            ri += 1

    ret.append( (float("inf") , float("inf")) )
    return ret

N = int(input())
p = list(map(int,input().split()))


ominL = []
eminL = []
for i in range(N):
    if i % 2 == 0:
        ominL.append( (float("inf"),i) )
        eminL.append( ( p[i] , i ) )
    else:
        eminL.append( (float("inf"),i) )
        ominL.append( ( p[i] , i ) )

emin = make_SparseTable(eminL)
omin = make_SparseTable(ominL)

#print (emin)

ans = want(0,N-1)
alis = []
for i in range(N//2):
    alis.append(ans[i][0])
    alis.append(ans[i][1])
print (*alis)

Submission status: Time Limit Exceeded

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)])]
    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])

    def search_even(lower, upper):
        ret = 200000
        l, r = lower+num, upper+num
        while l < r:
            if r % 2 == 0:
                r -= 1
                ret = min(ret, tree_even[r])
            if l % 2 == 0:
                ret = min(ret, tree_even[l])
                l += 1
            l >>= 1
            r >>= 1
        return ret

    def search_odd(lower, upper):
        ret = 200000
        l, r = lower+num, upper+num
        while l < r:
            if r % 2 == 0:
                r -= 1
                ret = min(ret, tree_odd[r])
            if l % 2 == 0:
                ret = min(ret, tree_odd[l])
                l += 1
            l >>= 1
            r >>= 1
        return ret

    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 = search_even(i1, j1)
            even_idx = pos[even]
            odd = search_odd(even_idx >> 1, j1)
            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 = search_odd(i1, j1)
            odd_idx = pos[odd]
            even = search_even((odd_idx >> 1)+1, j1+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()

Submission status: Time Limit Exceeded

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)])]
    basesize = n >> 1
    num = 1
    while num < basesize:
        num *= 2
    num -= 1

    tree_even = [200000]*(num*2+1)
    tree_odd = [200000]*(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], tree_even[2*i+2])
    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], tree_odd[2*i+2])

    def search_even(lower, upper):
        ret = 200000
        l, r = lower+num, upper+num
        while l < r:
            if r % 2 == 0:
                r -= 1
                ret = min(ret, tree_even[r])
            if l % 2 == 0:
                ret = min(ret, tree_even[l])
                l += 1
            l >>= 1
            r >>= 1
        return ret

    def search_odd(lower, upper):
        ret = 200000
        l, r = lower+num, upper+num
        while l < r:
            if r % 2 == 0:
                r -= 1
                ret = min(ret, tree_odd[r])
            if l % 2 == 0:
                ret = min(ret, tree_odd[l])
                l += 1
            l >>= 1
            r >>= 1
        return ret

    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 = search_even(i1, j1)
            even_idx = pos[even]
            odd = search_odd(even_idx//2, j1)
            odd_idx = 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 = search_odd(i1, j1)
            odd_idx = pos[odd]
            even = search_even(odd_idx//2+1, j1+1)
            even_idx = pos[even]
            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: Time Limit Exceeded

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)])]
    basesize = n >> 1
    num = 1
    while num < basesize:
        num *= 2
    num -= 1

    class segtree():
        def __init__(self, base):
            self.tree = [200000]*(num*2+1)
            tree = self.tree
            for i in range(num, num+basesize):
                tree[i] = base[i-num]
            for i in range(num-1, -1, -1):
                tree[i] = min(tree[2*i+1], tree[2*i+2])

        def search(self, lower, upper):
            ret = 200000
            l, r, tree = lower+num, upper+num, self.tree
            while l < r:
                if r % 2 == 0:
                    r -= 1
                    ret = min(ret, tree[r])
                if l % 2 == 0:
                    ret = min(ret, tree[l])
                    l += 1
                l >>= 1
                r >>= 1
            return ret

    seg_even = segtree(p[::2])
    seg_odd = segtree(p[1::2])

    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)
            even_idx = pos[even]
            odd = seg_odd.search(even_idx//2, j1)
            odd_idx = 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)
            odd_idx = pos[odd]
            even = seg_even.search(odd_idx//2+1, j1+1)
            even_idx = pos[even]
            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: Time Limit Exceeded

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)
            even_idx = pos[even]
            odd = seg_odd.search(even_idx//2, j1)
            odd_idx = 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)
            odd_idx = pos[odd]
            even = seg_even.search(odd_idx//2+1, j1+1)
            even_idx = pos[even]
            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()