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:
import sys
from heapq import heappop, heappush


class SegTreeMin:
    """
    以下のクエリを処理する
    1.update:  i番目の値をxに更新する
    2.get_min: 区間[l, r)の最小値を得る
    """

    def __init__(self, n, INF):
        """
        :param n: 要素数
        :param INF: 初期値（入りうる要素より十分に大きな数）
        """
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.tree = [INF] * (n2 << 1)
        self.INF = INF

    @classmethod
    def from_array(cls, arr, INF):
        ins = cls(len(arr), INF)
        ins.tree[ins.offset:ins.offset + len(arr)] = arr
        for i in range(ins.offset - 1, 0, -1):
            l = i << 1
            r = l + 1
            ins.tree[i] = min(ins.tree[l], ins.tree[r])
        return ins

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.offset
        self.tree[i] = x
        while i > 1:
            y = self.tree[i ^ 1]
            if y <= x:
                break
            i >>= 1
            self.tree[i] = x

    def get_min(self, a, b):
        """
        [a, b)の最小値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        result = self.INF

        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result = min(result, self.tree[r - 1])
            if l & 1:
                result = min(result, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1

        return result


def register(l, r, sgt, indices, heap, data):
    if l == r:
        return
    k = l % 2
    np = sgt[k].get_min(l, r)
    ni = indices[np]
    nq = sgt[k ^ 1].get_min(ni, r)
    nj = indices[nq]
    heappush(heap, np)
    data[np] = (nq, l, r, ni, nj)


n, *ppp = map(int, sys.stdin.buffer.read().split())
INF = 10 ** 18
indices = [0] * (n + 1)
even_p = [INF] * n
odd_p = [INF] * n
for i, p in enumerate(ppp):
    indices[p] = i
    if i % 2 == 0:
        even_p[i] = p
    else:
        odd_p[i] = p

sgt0 = SegTreeMin.from_array(even_p, INF)
sgt1 = SegTreeMin.from_array(odd_p, INF)
sgt = [sgt0, sgt1]
ans = []
heap = []
data = {}
register(0, n, sgt, indices, heap, data)
while heap:
    p = heappop(heap)
    q, l, r, i, j = data.pop(p)
    ans.append(p)
    ans.append(q)
    register(l, i, sgt, indices, heap, data)
    register(i + 1, j, sgt, indices, heap, data)
    register(j + 1, r, sgt, indices, heap, data)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappop, heappush


class SegTreeMin:
    """
    以下のクエリを処理する
    1.update:  i番目の値をxに更新する
    2.get_min: 区間[l, r)の最小値を得る
    """

    def __init__(self, n, INF):
        """
        :param n: 要素数
        :param INF: 初期値（入りうる要素より十分に大きな数）
        """
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.tree = [INF] * (n2 << 1)
        self.INF = INF

    @classmethod
    def from_array(cls, arr, INF):
        ins = cls(len(arr), INF)
        ins.tree[ins.offset:ins.offset + len(arr)] = arr
        for i in range(ins.offset - 1, 0, -1):
            l = i << 1
            r = l + 1
            ins.tree[i] = min(ins.tree[l], ins.tree[r])
        return ins

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.offset
        self.tree[i] = x
        while i > 1:
            y = self.tree[i ^ 1]
            if y <= x:
                break
            i >>= 1
            self.tree[i] = x

    def get_min(self, a, b):
        """
        [a, b)の最小値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        result = self.INF

        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result = min(result, self.tree[r - 1])
            if l & 1:
                result = min(result, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1

        return result


n, *ppp = map(int, sys.stdin.buffer.read().split())
INF = 10 ** 18
indices = [0] * (n + 1)
even_p = [INF] * n
odd_p = [INF] * n
for i, p in enumerate(ppp):
    indices[p] = i
    if i % 2 == 0:
        even_p[i] = p
    else:
        odd_p[i] = p

sgt0 = SegTreeMin.from_array(even_p, INF)
sgt1 = SegTreeMin.from_array(odd_p, INF)
sgt = [sgt0, sgt1]
ans = []
heap = []
data = {}
first_p = sgt0.get_min(0, n)
i = indices[first_p]
first_q = sgt1.get_min(i, n)
j = indices[first_q]
heap.append(first_p)
data[first_p] = (first_q, 0, n, i, j)
while heap:
    p = heappop(heap)
    q, l, r, i, j = data.pop(p)
    ans.append(p)
    ans.append(q)
    if l < i:
        k = l % 2
        np = sgt[k].get_min(l, i)
        ni = indices[np]
        nq = sgt[k ^ 1].get_min(ni, i)
        nj = indices[nq]
        heappush(heap, np)
        data[np] = (nq, l, i, ni, nj)
    if i + 1 < j:
        k = (i + 1) % 2
        np = sgt[k].get_min(i + 1, j)
        ni = indices[np]
        nq = sgt[k ^ 1].get_min(ni, j)
        nj = indices[nq]
        heappush(heap, np)
        data[np] = (nq, i + 1, j, ni, nj)
    if j + 1 < r:
        k = (j + 1) % 2
        np = sgt[k].get_min(j + 1, r)
        ni = indices[np]
        nq = sgt[k ^ 1].get_min(ni, r)
        nj = indices[nq]
        heappush(heap, np)
        data[np] = (nq, j + 1, r, ni, nj)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappop, heappush


class SegTreeMin:
    """
    以下のクエリを処理する
    1.update:  i番目の値をxに更新する
    2.get_min: 区間[l, r)の最小値を得る
    """

    def __init__(self, n, INF):
        """
        :param n: 要素数
        :param INF: 初期値（入りうる要素より十分に大きな数）
        """
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.tree = [INF] * (n2 << 1)
        self.INF = INF

    @classmethod
    def from_array(cls, arr, INF):
        ins = cls(len(arr), INF)
        ins.tree[ins.offset:ins.offset + len(arr)] = arr
        for i in range(ins.offset - 1, 0, -1):
            l = i << 1
            r = l + 1
            ins.tree[i] = min(ins.tree[l], ins.tree[r])
        return ins

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.offset
        self.tree[i] = x
        while i > 1:
            y = self.tree[i ^ 1]
            if y <= x:
                break
            i >>= 1
            self.tree[i] = x

    def get_min(self, a, b):
        """
        [a, b)の最小値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        result = self.INF

        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result = min(result, self.tree[r - 1])
            if l & 1:
                result = min(result, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1

        return result


n, *ppp = map(int, sys.stdin.buffer.read().split())
INF = 10 ** 18

sgt0 = SegTreeMin.from_array([(p if i % 2 == 0 else INF, i) for i, p in enumerate(ppp)], (INF, -1))
sgt1 = SegTreeMin.from_array([(p if i % 2 == 1 else INF, i) for i, p in enumerate(ppp)], (INF, -1))
sgt = [sgt0, sgt1]
ans = []
heap = []
data = {}
first_p, i = sgt0.get_min(0, n)
first_q, j = sgt1.get_min(i, n)
heap.append(first_p)
data[first_p] = (first_q, 0, n, i, j)
while heap:
    p = heappop(heap)
    q, l, r, i, j = data.pop(p)
    ans.append(p)
    ans.append(q)
    if l < i:
        k = l % 2
        np, ni = sgt[k].get_min(l, i)
        nq, nj = sgt[k ^ 1].get_min(ni, i)
        heappush(heap, np)
        data[np] = (nq, l, i, ni, nj)
    if i + 1 < j:
        k = (i + 1) % 2
        np, ni = sgt[k].get_min(i + 1, j)
        nq, nj = sgt[k ^ 1].get_min(ni, j)
        heappush(heap, np)
        data[np] = (nq, i + 1, j, ni, nj)
    if j + 1 < r:
        k = (j + 1) % 2
        np, ni = sgt[k].get_min(j + 1, r)
        nq, nj = sgt[k ^ 1].get_min(ni, r)
        heappush(heap, np)
        data[np] = (nq, j + 1, r, ni, nj)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappop, heappush


class SegTreeMin:
    """
    以下のクエリを処理する
    1.update:  i番目の値をxに更新する
    2.get_min: 区間[l, r)の最小値を得る
    """

    def __init__(self, n, INF):
        """
        :param n: 要素数
        :param INF: 初期値（入りうる要素より十分に大きな数）
        """
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.tree = [INF] * (n2 << 1)
        self.INF = INF

    @classmethod
    def from_array(cls, arr, INF):
        ins = cls(len(arr), INF)
        ins.tree[ins.offset:ins.offset + len(arr)] = arr
        for i in range(ins.offset - 1, 0, -1):
            l = i << 1
            r = l + 1
            ins.tree[i] = min(ins.tree[l], ins.tree[r])
        return ins

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.offset
        self.tree[i] = x
        while i > 1:
            y = self.tree[i ^ 1]
            if y <= x:
                break
            i >>= 1
            self.tree[i] = x

    def get_min(self, a, b):
        """
        [a, b)の最小値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        result = self.INF

        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result = min(result, self.tree[r - 1])
            if l & 1:
                result = min(result, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1

        return result


n, *ppp = map(int, sys.stdin.buffer.read().split())
INF = 10 ** 18

sgt0 = SegTreeMin.from_array([(p if i % 2 == 0 else INF, i) for i, p in enumerate(ppp)], (INF, -1))
sgt1 = SegTreeMin.from_array([(p if i % 2 == 1 else INF, i) for i, p in enumerate(ppp)], (INF, -1))
sgt = [sgt0, sgt1]
ans = []
heap = []
first_p, i = sgt0.get_min(0, n)
first_q, j = sgt1.get_min(i, n)
heap.append((first_p, first_q, 0, n, i, j))
while heap:
    p, q, l, r, i, j = heappop(heap)
    ans.append(p)
    ans.append(q)
    if l < i:
        k = l % 2
        np, ni = sgt[k].get_min(l, i)
        nq, nj = sgt[k ^ 1].get_min(ni, i)
        heappush(heap, (np, nq, l, i, ni, nj))
    if i + 1 < j:
        k = (i + 1) % 2
        np, ni = sgt[k].get_min(i + 1, j)
        nq, nj = sgt[k ^ 1].get_min(ni, j)
        heappush(heap, (np, nq, i + 1, j, ni, nj))
    if j + 1 < r:
        k = (j + 1) % 2
        np, ni = sgt[k].get_min(j + 1, r)
        nq, nj = sgt[k ^ 1].get_min(ni, r)
        heappush(heap, (np, nq, j + 1, r, ni, nj))

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
# AOJ DSL_2_A "Range Minimum Query"
# SegmantTreeの実装
import sys
input = sys.stdin.readline

# 初期化最大値
INF = (1 << 31) - 1

class SegmentTree:
    def __init__(self, N):
        self.N = 2**(N-1).bit_length()
        self.data = [[INF, -1] for _ in range(2*self.N-1)]
    
    # O(N)で初期化
    def compose(self, A):
        for k, a in enumerate(A):
            self.data[k+self.N-1] = [a, k]
        first = self.N - 1
        while first > 0:
            first = (first-1)//2
            for k in range(first, 2*first+1):
                if self.data[2*k+1][0] < self.data[2*k+2][0]:
                    self.data[k] = self.data[2*k+1][:]
                else:
                    self.data[k] = self.data[2*k+2][:]

    # k番目の値(0-indexed)をaに変更
    def update(self, k, a):
        self.data[k+self.N-1] = [a, k]
        k += self.N - 1
        while k > 0:
            k = (k-1)//2
            if self.data[2*k+1][0] < self.data[2*k+2][0]:
                self.data[k] = self.data[2*k+1][:]
            else:
                self.data[k] = self.data[2*k+2][:]

    # [l, r)の最小値取得
    # kがNodeの番号、対応する区間が[a, b)
    def query_min(self, l, r):
        if l+1 == r:
            return self.data[l+self.N-1]
        L = l + self.N
        R = r + self.N
        s = [INF, -1]
        while L < R:
            if R & 1:
                R -= 1
                if s[0] > self.data[R-1][0]:
                    s = self.data[R-1]
            if L & 1:
                if s[0] > self.data[L-1][0]:
                    s = self.data[L-1]
                L += 1
            L >>= 1; R >>= 1
        return s

import heapq as hp
N = int(input())
A = list(map(int, input().split()))

def main():
    ST1 = SegmentTree(N//2)
    ST2 = SegmentTree(N//2)
    ST1.compose(A[::2])
    ST2.compose(A[1::2])

    ans = []
    q = []
    v, k = ST1.query_min(0, N//2)
    dic = {}
    dic[v] = (k, 0, N//2, True)
    hp.heappush(q, v)
    for _ in range(N//2):
        valuea = hp.heappop(q)
        ka, l, r, is1 = dic[valuea]
        ans.append(str(valuea))
        if is1:
            valueb, kb = ST2.query_min(ka, r)
            if ka < kb:
                m2, nk2 = ST2.query_min(ka, kb)
                hp.heappush(q, m2)
                dic[m2] = (nk2, ka, kb+1, False)
            if l < ka:
                m1, nk1 = ST1.query_min(l, ka)
                hp.heappush(q, m1)
                dic[m1] = (nk1, l, ka, True)
            if kb+1 < r:
                m3, nk3 = ST1.query_min(kb+1, r)
                hp.heappush(q, m3)
                dic[m3] = (nk3, kb+1, r, True)
        else:
            valueb, kb = ST1.query_min(ka+1, r)
            if ka+1 < kb:
                m1, nk1 = ST1.query_min(ka+1, kb)
                hp.heappush(q, m1)
                dic[m1] = (nk1, ka+1, kb, True)
            if l < ka:
                m2, nk2 = ST2.query_min(l, ka)
                hp.heappush(q, m2)
                dic[m2] = (nk2, l, ka+1, False)
            if kb < r-1:
                m3, nk3 = ST2.query_min(kb, r-1)
                hp.heappush(q, m3)
                dic[m3] = (nk3, kb, r, False)

        ans.append(str(valueb))

    print(" ".join(ans))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# AOJ DSL_2_A "Range Minimum Query"
# SegmantTreeの実装
import sys
input = sys.stdin.readline

# 初期化最大値
INF = (1 << 31) - 1

class SegmentTree:
    def __init__(self, N):
        self.N = 2**(N-1).bit_length()
        self.data = [[INF, -1] for _ in range(2*self.N-1)]
    
    # O(N)で初期化
    def compose(self, A):
        for k, a in enumerate(A):
            self.data[k+self.N-1] = [a, k]
        first = self.N - 1
        while first > 0:
            first = (first-1)//2
            for k in range(first, 2*first+1):
                if self.data[2*k+1][0] < self.data[2*k+2][0]:
                    self.data[k] = self.data[2*k+1][:]
                else:
                    self.data[k] = self.data[2*k+2][:]

    # k番目の値(0-indexed)をaに変更
    def update(self, k, a):
        self.data[k+self.N-1] = [a, k]
        k += self.N - 1
        while k > 0:
            k = (k-1)//2
            if self.data[2*k+1][0] < self.data[2*k+2][0]:
                self.data[k] = self.data[2*k+1][:]
            else:
                self.data[k] = self.data[2*k+2][:]

    # [l, r)の最小値取得
    # kがNodeの番号、対応する区間が[a, b)
    def query_min(self, l, r):
        if l+1 == r:
            return self.data[l+self.N-1]
        L = l + self.N
        R = r + self.N
        s = [INF, -1]
        while L < R:
            if R & 1:
                R -= 1
                if s[0] > self.data[R-1][0]:
                    s = self.data[R-1]
            if L & 1:
                if s[0] > self.data[L-1][0]:
                    s = self.data[L-1]
                L += 1
            L >>= 1; R >>= 1
        return s

import heapq as hp
N = int(input())
A = list(map(int, input().split()))

def main():
    ST1 = SegmentTree(N//2)
    ST2 = SegmentTree(N//2)
    A1 = []
    A2 = []
    for i,a in enumerate(A):
        if i%2==0:
            A1.append(a)
        else:
            A2.append(a)
    ST1.compose(A1)
    ST2.compose(A2)

    ans = []
    q = []
    v, k = ST1.query_min(0, N//2)
    dic = {}
    dic[v] = (k, 0, N//2, True)
    hp.heappush(q, v)
    for _ in range(N//2):
        valuea = hp.heappop(q)
        ka, l, r, is1 = dic[valuea]
        ans.append(str(valuea))
        if is1:
            valueb, kb = ST2.query_min(ka, r)
            if ka < kb:
                m2, nk2 = ST2.query_min(ka, kb)
                hp.heappush(q, m2)
                dic[m2] = (nk2, ka, kb+1, False)
            if l < ka:
                m1, nk1 = ST1.query_min(l, ka)
                hp.heappush(q, m1)
                dic[m1] = (nk1, l, ka, True)
            if kb+1 < r:
                m3, nk3 = ST1.query_min(kb+1, r)
                hp.heappush(q, m3)
                dic[m3] = (nk3, kb+1, r, True)
        else:
            valueb, kb = ST1.query_min(ka+1, r)
            if ka+1 < kb:
                m1, nk1 = ST1.query_min(ka+1, kb)
                hp.heappush(q, m1)
                dic[m1] = (nk1, ka+1, kb, True)
            if l < ka:
                m2, nk2 = ST2.query_min(l, ka)
                hp.heappush(q, m2)
                dic[m2] = (nk2, l, ka+1, False)
            if kb < r-1:
                m3, nk3 = ST2.query_min(kb, r-1)
                hp.heappush(q, m3)
                dic[m3] = (nk3, kb, r, False)

        ans.append(str(valueb))

    print(" ".join(ans))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# AOJ DSL_2_A "Range Minimum Query"
# SegmantTreeの実装
import sys
input = sys.stdin.readline

# 初期化最大値
INF = (1 << 31) - 1

class SegmentTree:
    def __init__(self, N):
        self.N = 2**(N-1).bit_length()
        self.data = [[INF, -1] for _ in range(2*self.N-1)]

    # k番目の値(0-indexed)をaに変更
    def update(self, k, a):
        self.data[k+self.N-1] = [a, k]
        k += self.N - 1
        while k > 0:
            k = (k-1)//2
            if self.data[2*k+1][0] < self.data[2*k+2][0]:
                self.data[k] = self.data[2*k+1][:]
            else:
                self.data[k] = self.data[2*k+2][:]

    # [l, r)の最小値取得
    # kがNodeの番号、対応する区間が[a, b)
    def query_min(self, l, r):
        if l+1 == r:
            return self.data[l+self.N-1]
        L = l + self.N
        R = r + self.N
        s = [INF, -1]
        while L < R:
            if R & 1:
                R -= 1
                if s[0] > self.data[R-1][0]:
                    s = self.data[R-1]
            if L & 1:
                if s[0] > self.data[L-1][0]:
                    s = self.data[L-1]
                L += 1
            L >>= 1; R >>= 1
        return s

import heapq as hp
N = int(input())
A = list(map(int, input().split()))

def main():
    ST1 = SegmentTree(N//2)
    ST2 = SegmentTree(N//2)
    for i,a in enumerate(A):
        if i%2==0:
            ST1.update(i//2, a)
        else:
            ST2.update(i//2, a)

    ans = []
    q = []
    v, k = ST1.query_min(0, N//2)
    dic = {}
    dic[v] = (k, 0, N//2, True)
    hp.heappush(q, v)
    for _ in range(N//2):
        valuea = hp.heappop(q)
        ka, l, r, is1 = dic[valuea]
        ans.append(str(valuea))
        if is1:
            valueb, kb = ST2.query_min(ka, r)
            if ka < kb:
                m2, nk2 = ST2.query_min(ka, kb)
                hp.heappush(q, m2)
                dic[m2] = (nk2, ka, kb+1, False)
            if l < ka:
                m1, nk1 = ST1.query_min(l, ka)
                hp.heappush(q, m1)
                dic[m1] = (nk1, l, ka, True)
            if kb+1 < r:
                m3, nk3 = ST1.query_min(kb+1, r)
                hp.heappush(q, m3)
                dic[m3] = (nk3, kb+1, r, True)
        else:
            valueb, kb = ST1.query_min(ka+1, r)
            if ka+1 < kb:
                m1, nk1 = ST1.query_min(ka+1, kb)
                hp.heappush(q, m1)
                dic[m1] = (nk1, ka+1, kb, True)
            if l < ka:
                m2, nk2 = ST2.query_min(l, ka)
                hp.heappush(q, m2)
                dic[m2] = (nk2, l, ka+1, False)
            if kb < r-1:
                m3, nk3 = ST2.query_min(kb, r-1)
                hp.heappush(q, m3)
                dic[m3] = (nk3, kb, r, False)

        ans.append(str(valueb))

    print(" ".join(ans))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# AOJ DSL_2_A "Range Minimum Query"
# SegmantTreeの実装
import sys
input = sys.stdin.readline

# 初期化最大値
INF = (1 << 31) - 1

class SegmentTree:
    def __init__(self, N):
        self.N = 2**(N-1).bit_length()
        self.data = [[INF, -1] for _ in range(2*self.N-1)]

    # k番目の値(0-indexed)をaに変更
    def update(self, k, a):
        self.data[k+self.N-1] = [a, k]
        k += self.N - 1
        while k > 0:
            k = (k-1)//2
            if self.data[2*k+1][0] < self.data[2*k+2][0]:
                self.data[k] = self.data[2*k+1][:]
            else:
                self.data[k] = self.data[2*k+2][:]

    # [l, r)の最小値取得
    # kがNodeの番号、対応する区間が[a, b)
    def query_min(self, l, r):
        L = l + self.N
        R = r + self.N
        s = [INF, -1]
        while L < R:
            if R & 1:
                R -= 1
                if s[0] > self.data[R-1][0]:
                    s = self.data[R-1]
            if L & 1:
                if s[0] > self.data[L-1][0]:
                    s = self.data[L-1]
                L += 1
            L >>= 1; R >>= 1
        return s

import heapq as hp
N = int(input())
A = list(map(int, input().split()))

def main():
    ST1 = SegmentTree(N//2)
    ST2 = SegmentTree(N//2)
    for i,a in enumerate(A):
        if i%2==0:
            ST1.update(i//2, a)
        else:
            ST2.update(i//2, a)

    ans = []
    q = []
    v, k = ST1.query_min(0, N//2)
    dic = {}
    dic[v] = (k, 0, N//2, True)
    hp.heappush(q, v)
    for _ in range(N//2):
        valuea = hp.heappop(q)
        ka, l, r, is1 = dic[valuea]
        ans.append(str(valuea))
        if is1:
            valueb, kb = ST2.query_min(ka, r)
            if ka < kb:
                m2, nk2 = ST2.query_min(ka, kb)
                hp.heappush(q, m2)
                dic[m2] = (nk2, ka, kb+1, False)
            if l < ka:
                m1, nk1 = ST1.query_min(l, ka)
                hp.heappush(q, m1)
                dic[m1] = (nk1, l, ka, True)
            if kb+1 < r:
                m3, nk3 = ST1.query_min(kb+1, r)
                hp.heappush(q, m3)
                dic[m3] = (nk3, kb+1, r, True)
        else:
            valueb, kb = ST1.query_min(ka+1, r)
            if ka+1 < kb:
                m1, nk1 = ST1.query_min(ka+1, kb)
                hp.heappush(q, m1)
                dic[m1] = (nk1, ka+1, kb, True)
            if l < ka:
                m2, nk2 = ST2.query_min(l, ka)
                hp.heappush(q, m2)
                dic[m2] = (nk2, l, ka+1, False)
            if kb < r-1:
                m3, nk3 = ST2.query_min(kb, r-1)
                hp.heappush(q, m3)
                dic[m3] = (nk3, kb, r, False)

        ans.append(str(valueb))

    print(" ".join(ans))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# AOJ DSL_2_A "Range Minimum Query"
# SegmantTreeの実装
import sys
input = sys.stdin.readline

# 初期化最大値
INF = (1 << 31) - 1

class SegmentTree:
    def __init__(self, N):
        self.N = 2**(N-1).bit_length()
        self.data = [[INF, -1] for _ in range(2*self.N-1)]

    # k番目の値(0-indexed)をaに変更
    def update(self, k, a):
        self.data[k+self.N-1] = [a, k]
        k += self.N - 1
        while k > 0:
            k = (k-1)//2
            if self.data[2*k+1][0] < self.data[2*k+2][0]:
                self.data[k] = self.data[2*k+1][:]
            else:
                self.data[k] = self.data[2*k+2][:]

    # [l, r)の最小値取得
    # kがNodeの番号、対応する区間が[a, b)
    def query_min(self, l, r):
        L = l + self.N
        R = r + self.N
        s = [INF, -1]
        while L < R:
            if R & 1:
                R -= 1
                if s[0] > self.data[R-1][0]:
                    s = self.data[R-1]
            if L & 1:
                if s[0] > self.data[L-1][0]:
                    s = self.data[L-1]
                L += 1
            L >>= 1; R >>= 1
        return s

import heapq as hp
N = int(input())
A = list(map(int, input().split()))

def main():
    ST1 = SegmentTree(N//2)
    ST2 = SegmentTree(N//2)
    for i,a in enumerate(A):
        if i%2==0:
            ST1.update(i//2, a)
        else:
            ST2.update(i//2, a)

    ans = []
    q = []
    v, k = ST1.query_min(0, N//2)
    hp.heappush(q, (v, k, 0, N//2, True))
    for _ in range(N//2):
        valuea, ka, l, r, is1 = hp.heappop(q)
        ans.append(str(valuea))
        if is1:
            valueb, kb = ST2.query_min(ka, r)
            if ka < kb:
                m2, nk2 = ST2.query_min(ka, kb)
                hp.heappush(q, (m2, nk2, ka, kb+1, False))
            if l < ka:
                m1, nk1 = ST1.query_min(l, ka)
                hp.heappush(q, (m1, nk1, l, ka, True))
            if kb+1 < r:
                m3, nk3 = ST1.query_min(kb+1, r)
                hp.heappush(q, (m3, nk3, kb+1, r, True))
        else:
            valueb, kb = ST1.query_min(ka+1, r)
            if ka+1 < kb:
                m1, nk1 = ST1.query_min(ka+1, kb)
                hp.heappush(q, (m1, nk1, ka+1, kb, True))
            if l < ka:
                m2, nk2 = ST2.query_min(l, ka)
                hp.heappush(q, (m2, nk2, l, ka+1, False))
            if kb < r-1:
                m3, nk3 = ST2.query_min(kb, r-1)
                hp.heappush(q, (m3, nk3, kb, r, False))

        ans.append(str(valueb))

    print(" ".join(ans))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# AOJ DSL_2_A "Range Minimum Query"
# SegmantTreeの実装
import sys
input = sys.stdin.readline

# 初期化最大値
INF = (1 << 31) - 1

class SegmentTree:
    def __init__(self, N):
        self.N = 2**(N-1).bit_length()
        self.data = [[INF, -1] for _ in range(2*self.N-1)]

    # k番目の値(0-indexed)をaに変更
    def update(self, k, a):
        self.data[k+self.N-1] = [a, k]
        k += self.N - 1
        while k > 0:
            k = (k-1)//2
            if self.data[2*k+1][0] < self.data[2*k+2][0]:
                self.data[k] = self.data[2*k+1][:]
            else:
                self.data[k] = self.data[2*k+2][:]

    # [l, r)の最小値取得
    # kがNodeの番号、対応する区間が[a, b)
    def query_min(self, l, r):
        L = l + self.N
        R = r + self.N
        s = [INF, -1]
        while L < R:
            if R & 1:
                R -= 1
                if s[0] > self.data[R-1][0]:
                    s = self.data[R-1]
            if L & 1:
                if s[0] > self.data[L-1][0]:
                    s = self.data[L-1]
                L += 1
            L >>= 1; R >>= 1
        return s

import heapq as hp
N = int(input())
A = list(map(int, input().split()))

ST1 = SegmentTree(N//2)
ST2 = SegmentTree(N//2)
for i,a in enumerate(A):
    if i%2==0:
        ST1.update(i//2, a)
    else:
        ST2.update(i//2, a)

ans = []
q = []
v, k = ST1.query_min(0, N//2)
hp.heappush(q, (v, k, 0, N//2, True))
for _ in range(N//2):
    valuea, ka, l, r, is1 = hp.heappop(q)
    ans.append(valuea)
    if is1:
        valueb, kb = ST2.query_min(ka, r)
        if ka < kb:
            m2, nk2 = ST2.query_min(ka, kb)
            hp.heappush(q, (m2, nk2, ka, kb+1, False))
        if l < ka:
            m1, nk1 = ST1.query_min(l, ka)
            hp.heappush(q, (m1, nk1, l, ka, True))
        if kb+1 < r:
            m3, nk3 = ST1.query_min(kb+1, r)
            hp.heappush(q, (m3, nk3, kb+1, r, True))
    else:
        valueb, kb = ST1.query_min(ka+1, r)
        if ka+1 < kb:
            m1, nk1 = ST1.query_min(ka+1, kb)
            hp.heappush(q, (m1, nk1, ka+1, kb, True))
        if l < ka:
            m2, nk2 = ST2.query_min(l, ka)
            hp.heappush(q, (m2, nk2, l, ka, False))
        if kb < r-1:
            m3, nk3 = ST2.query_min(kb, r-1)
            hp.heappush(q, (m3, nk3, kb, r-1, False))

    ans.append(valueb)

print(*ans)