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
import heapq


class SegmentTree:
    def __init__(self, _n):
        n = 1
        while n < _n:
            n *= 2
        self.n = n
        self.dat = [(sys.maxsize, i) for i in range(0, 2 * n - 1)]

    def update(self, _k, _a):
        _k += self.n - 1
        self.dat[_k] = _a
        while 0 < _k:
            _k = (_k - 1) // 2
            self.dat[_k] = min(self.dat[_k * 2 + 1], self.dat[_k * 2 + 2], key=(lambda x: x[0]))

    def query(self, _a, _b, _k, _l, _r):
        if _r <= _a or _b <= _l:
            return (sys.maxsize, 0)

        if _a <= _l and _r <= _b:
            return self.dat[_k]
        else:
            vl = self.query(_a, _b, _k * 2 + 1, _l, (_l + _r) // 2)
            vr = self.query(_a, _b, _k * 2 + 2, (_l + _r) // 2, _r)
            return min(vl, vr, key=(lambda x: x[0]))


if __name__ == '__main__':
    N = int(input())
    p = list(map(int, input().split()))

    segtree_odd = SegmentTree(N)
    segtree_even = SegmentTree(N)
    for i in range(0, N):
        if i % 2 == 0:
            segtree_even.update(i, (p[i], i))
        else:
            segtree_odd.update(i, (p[i], i))
    pq = []
    heapq.heappush(pq, (segtree_even.query(0, N, 0, 0, N)[0], 0, N))
    ans = []
    while len(ans) != N:
        target_range = heapq.heappop(pq)
        if target_range[1] % 2 == 0:
            tmp_even_min = segtree_even.query(target_range[1], target_range[2], 0, 0, N)
            ans.append(tmp_even_min[0])
            tmp_odd_min = segtree_odd.query(tmp_even_min[1], target_range[2], 0, 0, N)
            ans.append(tmp_odd_min[0])

            # segtree_even.update(tmp_even_min[1], (sys.maxsize, tmp_even_min[1]))
            # segtree_odd.update(tmp_odd_min[1], (sys.maxsize, tmp_odd_min[1]))
            if target_range[1] + 1 != tmp_even_min[1]:
                heapq.heappush(pq, (
                    segtree_even.query(target_range[1], tmp_even_min[1], 0, 0, N)[0], target_range[1], tmp_even_min[1]))
            if tmp_even_min[1] + 1 != tmp_odd_min[1] - 1:
                heapq.heappush(pq, (
                    segtree_odd.query(tmp_even_min[1] + 1, tmp_odd_min[1], 0, 0, N)[0], tmp_even_min[1] + 1,
                    tmp_odd_min[1]))
            if tmp_odd_min[1] + 1 != target_range[2] - 1:
                heapq.heappush(pq, (
                    segtree_even.query(tmp_odd_min[1] + 1, target_range[2], 0, 0, N)[0], tmp_odd_min[1] + 1,
                    target_range[2]))
        else:
            tmp_odd_min = segtree_odd.query(target_range[1], target_range[2], 0, 0, N)
            ans.append(tmp_odd_min[0])
            tmp_even_min = segtree_even.query(tmp_odd_min[1], target_range[2], 0, 0, N)
            ans.append(tmp_even_min[0])

            # segtree_odd.update(tmp_odd_min[1], (sys.maxsize, tmp_odd_min[1]))
            # segtree_even.update(tmp_even_min[1], (sys.maxsize, tmp_even_min[1]))
            if target_range[1] + 1 != tmp_odd_min[1]:
                heapq.heappush(pq, (
                    segtree_odd.query(target_range[1], tmp_odd_min[1], 0, 0, N)[0], target_range[1], tmp_odd_min[1]))
            if tmp_odd_min[1] + 1 != tmp_even_min[1] - 1:
                heapq.heappush(pq, (
                    segtree_even.query(tmp_odd_min[1] + 1, tmp_even_min[1], 0, 0, N)[0], tmp_odd_min[1] + 1,
                    tmp_even_min[1]))
            if tmp_even_min[1] + 1 != target_range[2] - 1:
                heapq.heappush(pq, (
                    segtree_odd.query(tmp_even_min[1] + 1, target_range[2], 0, 0, N)[0], tmp_even_min[1] + 1,
                    target_range[2]))

    ans = list(map(str, ans))
    print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq


class SegmentTree:
    def __init__(self, _n):
        n = 1
        while n < _n:
            n *= 2
        self.n = n
        self.dat = [(sys.maxsize, i) for i in range(0, 2 * n - 1)]

    def update(self, _k, _a):
        _k += self.n - 1
        self.dat[_k] = _a
        while 0 < _k:
            _k = (_k - 1) // 2
            self.dat[_k] = min(self.dat[_k * 2 + 1], self.dat[_k * 2 + 2], key=(lambda x: x[0]))

    def query(self, _a, _b, _k, _l, _r):
        if _r <= _a or _b <= _l:
            return (sys.maxsize, 0)

        if _a <= _l and _r <= _b:
            return self.dat[_k]
        else:
            vl = self.query(_a, _b, _k * 2 + 1, _l, (_l + _r) // 2)
            vr = self.query(_a, _b, _k * 2 + 2, (_l + _r) // 2, _r)
            return min(vl, vr, key=(lambda x: x[0]))


if __name__ == '__main__':
    N = int(input())
    p = list(map(int, input().split()))

    segtree_odd = SegmentTree(N)
    segtree_even = SegmentTree(N)
    for i in range(0, N):
        if i % 2 == 0:
            segtree_even.update(i, (p[i], i))
        else:
            segtree_odd.update(i, (p[i], i))
    pq = []
    heapq.heappush(pq, (segtree_even.query(0, N, 0, 0, N)[0], 0, N))
    ans = []
    while len(ans) != N:
        target_range = heapq.heappop(pq)
        if target_range[1] % 2 == 0:
            tmp_even_min = segtree_even.query(target_range[1], target_range[2], 0, 0, N)
            ans.append(tmp_even_min[0])
            tmp_odd_min = segtree_odd.query(tmp_even_min[1], target_range[2], 0, 0, N)
            ans.append(tmp_odd_min[0])

            # segtree_even.update(tmp_even_min[1], (sys.maxsize, tmp_even_min[1]))
            # segtree_odd.update(tmp_odd_min[1], (sys.maxsize, tmp_odd_min[1]))

            heapq.heappush(pq, (
                segtree_even.query(target_range[1], tmp_even_min[1], 0, 0, N)[0], target_range[1], tmp_even_min[1]))
            heapq.heappush(pq, (
                segtree_odd.query(tmp_even_min[1] + 1, tmp_odd_min[1], 0, 0, N)[0], tmp_even_min[1] + 1,
                tmp_odd_min[1]))
            heapq.heappush(pq, (
                segtree_even.query(tmp_odd_min[1] + 1, target_range[2], 0, 0, N)[0], tmp_odd_min[1] + 1,
                target_range[2]))
        else:
            tmp_odd_min = segtree_odd.query(target_range[1], target_range[2], 0, 0, N)
            ans.append(tmp_odd_min[0])
            tmp_even_min = segtree_even.query(tmp_odd_min[1], target_range[2], 0, 0, N)
            ans.append(tmp_even_min[0])

            # segtree_odd.update(tmp_odd_min[1], (sys.maxsize, tmp_odd_min[1]))
            # segtree_even.update(tmp_even_min[1], (sys.maxsize, tmp_even_min[1]))

            heapq.heappush(pq, (
                segtree_odd.query(target_range[1], tmp_odd_min[1], 0, 0, N)[0], target_range[1], tmp_odd_min[1]))
            heapq.heappush(pq, (
                segtree_even.query(tmp_odd_min[1] + 1, tmp_even_min[1], 0, 0, N)[0], tmp_odd_min[1] + 1,
                tmp_even_min[1]))
            heapq.heappush(pq, (
                segtree_odd.query(tmp_even_min[1] + 1, target_range[2], 0, 0, N)[0], tmp_even_min[1] + 1,
                target_range[2]))

    ans = list(map(str, ans))
    print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq


class SegmentTree:
    def __init__(self, _n):
        n = 1
        while n < _n:
            n *= 2
        self.n = n
        self.dat = [(sys.maxsize, i) for i in range(0, 2 * n - 1)]

    def update(self, _k, _a):
        _k += self.n - 1
        self.dat[_k] = _a
        while 0 < _k:
            _k = (_k - 1) // 2
            self.dat[_k] = min(self.dat[_k * 2 + 1], self.dat[_k * 2 + 2], key=(lambda x: x[0]))

    def query(self, _a, _b, _k, _l, _r):
        if _r <= _a or _b <= _l:
            return (sys.maxsize, 0)

        if _a <= _l and _r <= _b:
            return self.dat[_k]
        else:
            vl = self.query(_a, _b, _k * 2 + 1, _l, (_l + _r) // 2)
            vr = self.query(_a, _b, _k * 2 + 2, (_l + _r) // 2, _r)
            return min(vl, vr, key=(lambda x: x[0]))


if __name__ == '__main__':
    N = int(input())
    p = list(map(int, input().split()))

    segtree_odd = SegmentTree(N)
    segtree_even = SegmentTree(N)
    for i in range(0, N):
        if i % 2 == 0:
            segtree_even.update(i, (p[i], i))
        else:
            segtree_odd.update(i, (p[i], i))
    pq = []
    heapq.heappush(pq, (segtree_even.query(0, N, 0, 0, N)[0], 0, N))
    ans = []
    while len(ans) != N:
        target_range = heapq.heappop(pq)
        if target_range[1] % 2 == 0:
            tmp_even_min = segtree_even.query(target_range[1], target_range[2], 0, 0, N)
            ans.append(tmp_even_min[0])
            tmp_odd_min = segtree_odd.query(tmp_even_min[1], target_range[2], 0, 0, N)
            ans.append(tmp_odd_min[0])

            segtree_even.update(tmp_even_min[1], (sys.maxsize, tmp_even_min[1]))
            segtree_odd.update(tmp_odd_min[1], (sys.maxsize, tmp_odd_min[1]))

            heapq.heappush(pq, (
                segtree_even.query(target_range[1], tmp_even_min[1], 0, 0, N)[0], target_range[1], tmp_even_min[1]))
            heapq.heappush(pq, (
                segtree_odd.query(tmp_even_min[1] + 1, tmp_odd_min[1], 0, 0, N)[0], tmp_even_min[1] + 1,
                tmp_odd_min[1]))
            heapq.heappush(pq, (
                segtree_even.query(tmp_odd_min[1] + 1, target_range[2], 0, 0, N)[0], tmp_odd_min[1] + 1,
                target_range[2]))
        else:
            tmp_odd_min = segtree_odd.query(target_range[1], target_range[2], 0, 0, N)
            ans.append(tmp_odd_min[0])
            tmp_even_min = segtree_even.query(tmp_odd_min[1], target_range[2], 0, 0, N)
            ans.append(tmp_even_min[0])

            segtree_odd.update(tmp_odd_min[1], (sys.maxsize, tmp_odd_min[1]))
            segtree_even.update(tmp_even_min[1], (sys.maxsize, tmp_even_min[1]))

            heapq.heappush(pq, (
                segtree_odd.query(target_range[1], tmp_odd_min[1], 0, 0, N)[0], target_range[1], tmp_odd_min[1]))
            heapq.heappush(pq, (
                segtree_even.query(tmp_odd_min[1] + 1, tmp_even_min[1], 0, 0, N)[0], tmp_odd_min[1] + 1,
                tmp_even_min[1]))
            heapq.heappush(pq, (
                segtree_odd.query(tmp_even_min[1] + 1, target_range[2], 0, 0, N)[0], tmp_even_min[1] + 1,
                target_range[2]))

    ans = list(map(str, ans))
    print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
import sys

class SegmentTree:
    INT_MAX = sys.maxsize

    def __init__(self, origData):
        self.origData = list(origData)
        n = len(self.origData)
        self.N = 1
        while self.N < n:
            self.N *= 2
        self.tree = [(SegmentTree.INT_MAX, 0)] * (self.N * 2 - 1)
        self.build()

    def build(self):
        # O(N)
        for i in range(len(self.origData)):
            self.update(i, self.origData[i])

    def update(self, i, x):
        # update value of index i to x : O(logN)
        idx = i
        i = self.N + i - 1;
        self.tree[i] = (x[0], x[1]);
        while i > 0:
            i = (i - 1) // 2
            self.tree[i] = self.merge(self.tree[i * 2 + 1], self.tree[i * 2 + 2])

    def query(self, start, end):
        # O(logN)
        return self.query_d(start, end, 0, 0, self.N)

    def query_d(self, a, b, k, l, r):
        if r <= a or b <= l:
            return (SegmentTree.INT_MAX, 0)
        if a <= l and r <= b:
            return self.tree[k]
        else:
            lv = self.query_d(a, b, 2 * k + 1, l, (l + r) // 2)  # to left side child node
            rb = self.query_d(a, b, 2 * k + 2, (l + r) // 2, r)  # to right side child node
            return self.merge(lv, rb)

    def merge(self, l, r):
        if l[0] <= r[0]:
            return l
        else:
            return r


def query(even_list, odd_list, start, end):
    if start % 2 == 0:
        return even_list.query(start // 2, (end + 1) // 2)
    else:
        return odd_list.query(start // 2, end // 2)

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

even_idx = []
odd_idx = []
for i, p_i in enumerate(p):
    if i % 2 == 0:
        even_idx.append((p_i, i))
    else:
        odd_idx.append((p_i, i))

even_list = SegmentTree(even_idx)
odd_list = SegmentTree(odd_idx)

#print(even_list.tree)
#print(odd_list.tree)

q = []
n0, idx0 = even_list.query(0, N // 2)
range_list = [(n0, idx0, 0, N)]
while len(range_list) > 0:
    n0, idx0, start, end = heappop(range_list)
    n1, idx1 = query(even_list, odd_list, idx0 + 1, end)
    q.append(n0)
    q.append(n1)
    #print(start, idx0, idx1, end, n0, n1)
    if start < idx0:
        n, idx = query(even_list, odd_list, start, idx0)
        heappush(range_list, (n, idx, start, idx0))
    if idx0 + 1 < idx1 - 1:
        n, idx = query(even_list, odd_list, idx0 + 1, idx1)
        heappush(range_list, (n, idx, idx0 + 1, idx1))
    if idx1 < end - 1:
        n, idx = query(even_list, odd_list, idx1 + 1, end)
        heappush(range_list, (n, idx, idx1 + 1, end))
    #print(range_list)

s = ' '.join([str(q_i) for q_i in q])
print(s)

Submission status: Time Limit Exceeded

Solution code:
import heapq
MAX_N = 1 << 17
INT_MAX = 2**31 - 1
 
class SegmentTree():
    def __init__(self, n_):
        self.n = 1
        while self.n < n_:
            self.n *= 2
        self.dat = [INT_MAX] * (2 * self.n - 1)
 
    def update(self, k, a):
        k += (self.n - 1)
        self.dat[k] = a
        while k > 0:
            k = (k - 1) // 2
            if self.dat[k * 2 + 1] < self.dat[k * 2 + 2]:
                self.dat[k] = self.dat[k * 2 + 1]
            else:
                self.dat[k] = self.dat[k * 2 + 2]
            # self.dat[k] = min(self.dat[k * 2 + 1], self.dat[k * 2 + 2])
 
    def query(self, a, b, k, l, r):
        if (r <= a) or (b <= l):
            return INT_MAX
        if (a <= l) and (r <= b):
            return self.dat[k]
        else:
            vl = self.query(a, b, k * 2 + 1, l, (l + r) // 2)
            vr = self.query(a, b, k * 2 + 2, (l + r) // 2, r)
            if vl < vr:
                return vl
            else:
                return vr
            # return min(vl, vr)
 
def wrap_query(type, a, b, k, l):
    if type == "even":
        if a % 2 == 0:
            ret = st_even.query(a, b, k, l, st_even.n)
        else:
            ret = st_odd.query(a, b, k, l, st_odd.n)
    else:
        if a % 2 == 0:
            ret = st_odd.query(a, b, k, l, st_odd.n)
        else:
            ret = st_even.query(a, b, k, l, st_even.n)
    return ret
 
class Item():
    def __init__(self, mini, left, right):
        self.mini = mini
        self.left = left
        self.right = right
 
if __name__ == '__main__':
    n = int(input())
    arr = list(map(int, input().split(" ")))
    st_even = SegmentTree(n)
    st_odd = SegmentTree(n)
    h = dict()
    for i in range(n):
        h[arr[i]] = i
        if i % 2 == 0:
            st_even.update(i, arr[i])
        else:
            st_odd.update(i, arr[i])
    q = [None] * n
    hq = []
    x = wrap_query("even", 0, n, 0, 0)
    heapq.heappush(hq, (x, Item(h[x], 0, n)))
    ii = 0
    while len(hq) != 0:
        q0, item = heapq.heappop(hq)
        l = item.left
        r = item.right
        i = item.mini
        q[ii] = q0
        ii += 1
        # q.append(q0)
        q1 = wrap_query("odd", i, r, 0, 0)
        j = h[q1]
        q[ii] = q1
        ii += 1
        # q.append(q1)
        if i - l > 1:
            x0 = wrap_query("even", l, i, 0, 0)
            heapq.heappush(hq, (x0, Item(h[x0], l, i)))
        if j - (i+1) > 1:
            x1 = wrap_query("even", i+1, j, 0, 0)
            heapq.heappush(hq, (x1, Item(h[x1], i+1, j)))
        if r - (j + 1) > 1:
            x2 = wrap_query("even", j+1, r, 0, 0)
            heapq.heappush(hq, (x2, Item(h[x2], j+1, r)))
    print(*q, sep=" ")

Submission status: Time Limit Exceeded

Solution code:
import heapq
MAX_N = 1 << 17
INT_MAX = 2**31 - 1

class SegmentTree():
    def __init__(self, n_):
        self.n = 1
        while self.n < n_:
            self.n *= 2
        self.dat = [INT_MAX] * (2 * self.n - 1)

    def update(self, k, a):
        k += (self.n - 1)
        self.dat[k] = a
        while k > 0:
            k = (k - 1) // 2
            if self.dat[k * 2 + 1] < self.dat[k * 2 + 2]:
                self.dat[k] = self.dat[k * 2 + 1]
            else:
                self.dat[k] = self.dat[k * 2 + 2]
            # self.dat[k] = min(self.dat[k * 2 + 1], self.dat[k * 2 + 2])

    def query(self, a, b, k, l, r):
        if (r <= a) or (b <= l):
            return INT_MAX
        if (a <= l) and (r <= b):
            return self.dat[k]
        else:
            vl = self.query(a, b, k * 2 + 1, l, (l + r) // 2)
            vr = self.query(a, b, k * 2 + 2, (l + r) // 2, r)
            if vl < vr:
                return vl
            else:
                return vr
            # return min(vl, vr)

def wrap_query(type, a, b, k, l):
    if type == "even":
        if a % 2 == 0:
            ret = st_even.query(a, b, k, l, st_even.n)
        else:
            ret = st_odd.query(a, b, k, l, st_odd.n)
    else:
        if a % 2 == 0:
            ret = st_odd.query(a, b, k, l, st_odd.n)
        else:
            ret = st_even.query(a, b, k, l, st_even.n)
    return ret

class Item():
    def __init__(self, mini, left, right):
        self.mini = mini
        self.left = left
        self.right = right

if __name__ == '__main__':
    n = int(input())
    arr = list(map(int, input().split(" ")))
    st_even = SegmentTree(n)
    st_odd = SegmentTree(n)
    h = dict()
    for i in range(n):
        h[arr[i]] = i
        if i % 2 == 0:
            st_even.update(i, arr[i])
        else:
            st_odd.update(i, arr[i])
    q = [None] * n
    hq = []
    x = wrap_query("even", 0, n, 0, 0)
    heapq.heappush(hq, (x, Item(h[x], 0, n)))
    ii = 0
    while len(hq) != 0:
        q0, item = heapq.heappop(hq)
        l = item.left
        r = item.right
        i = item.mini
        q[ii] = q0
        ii += 1
        # q.append(q0)
        q1 = wrap_query("odd", i, r, 0, 0)
        j = h[q1]
        q[ii] = q1
        ii += 1
        # q.append(q1)
        if i - l > 1:
            x0 = wrap_query("even", l, i, 0, 0)
            heapq.heappush(hq, (x0, Item(h[x0], l, i)))
        if j - (i+1) > 1:
            x1 = wrap_query("even", i+1, j, 0, 0)
            heapq.heappush(hq, (x1, Item(h[x1], i+1, j)))
        if r - (j + 1) > 1:
            x2 = wrap_query("even", j+1, r, 0, 0)
            heapq.heappush(hq, (x2, Item(h[x2], j+1, r)))
    print(*q, sep=" ")

Submission status: Time Limit Exceeded

Solution code:
import heapq
MAX_N = 1 << 17
INT_MAX = 2**31 - 1

class SegmentTree():
    def __init__(self, n_):
        self.n = 1
        while self.n < n_:
            self.n *= 2
        self.dat = [INT_MAX] * (2 * self.n - 1)

    def update(self, k, a):
        k += (self.n - 1)
        self.dat[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.dat[k] = min([self.dat[k * 2 + 1], self.dat[k * 2 + 2]])

    def query(self, a, b, k, l, r):
        if (r <= a) or (b <= l):
            return INT_MAX
        if (a <= l) and (r <= b):
            return self.dat[k]
        else:
            vl = self.query(a, b, k * 2 + 1, l, (l + r) // 2)
            vr = self.query(a, b, k * 2 + 2, (l + r) // 2, r)
            return min([vl, vr])

def wrap_query(type, a, b, k, l):
    if type == "even":
        if a % 2 == 0:
            ret = st_even.query(a, b, k, l, st_even.n)
        else:
            ret = st_odd.query(a, b, k, l, st_odd.n)
    else:
        if a % 2 == 0:
            ret = st_odd.query(a, b, k, l, st_odd.n)
        else:
            ret = st_even.query(a, b, k, l, st_even.n)
    return ret

class Item():
    def __init__(self, mini, left, right):
        self.mini = mini
        self.left = left
        self.right = right

if __name__ == '__main__':
    n = int(input())
    arr = list(map(int, input().split(" ")))
    st_even = SegmentTree(n)
    st_odd = SegmentTree(n)
    h = dict()
    for i in range(n):
        h[arr[i]] = i
        if i % 2 == 0:
            st_even.update(i, arr[i])
        else:
            st_odd.update(i, arr[i])
    q = []
    hq = []
    x = wrap_query("even", 0, n, 0, 0)
    heapq.heappush(hq, (x, Item(h[x], 0, n)))

    while len(hq) != 0:
        q0, item = heapq.heappop(hq)
        l = item.left
        r = item.right
        i = item.mini
        q.append(q0)
        q1 = wrap_query("odd", i, r, 0, 0)
        j = h[q1]
        q.append(q1)
        if i - l > 1:
            x0 = wrap_query("even", l, i, 0, 0)
            heapq.heappush(hq, (x0, Item(h[x0], l, i)))
        if j - (i+1) > 1:
            x1 = wrap_query("even", i+1, j, 0, 0)
            heapq.heappush(hq, (x1, Item(h[x1], i+1, j)))
        if r - (j + 1) > 1:
            x2 = wrap_query("even", j+1, r, 0, 0)
            heapq.heappush(hq, (x2, Item(h[x2], j+1, r)))
    print(*q, sep=" ")

Submission status: Time Limit Exceeded

Solution code:
import heapq

MAX_N = 1 << 17
INT_MAX = 2**31 - 1

class SegmentTree():
    def __init__(self, n_):
        self.n = 1
        while self.n < n_:
            self.n *= 2
        self.dat = [INT_MAX] * (2 * self.n - 1)

    def update(self, k, a):
        k += (self.n - 1)
        self.dat[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.dat[k] = min(self.dat[k * 2 + 1], self.dat[k * 2 + 2])

    def query(self, a, b, k, l, r):
        if (r <= a) or (b <= l):
            return INT_MAX
        if (a <= l) and (r <= b):
            return self.dat[k]
        else:
            vl = self.query(a, b, k * 2 + 1, l, (l + r) // 2)
            vr = self.query(a, b, k * 2 + 2, (l + r) // 2, r)
            return min(vl, vr)

def wrap_query(type, a, b, k, l):
    if type == "even":
        if a % 2 == 0:
            ret = st_even.query(a, b, k, l, st_even.n)
        else:
            ret = st_odd.query(a, b, k, l, st_odd.n)
    else:
        if a % 2 == 0:
            ret = st_odd.query(a, b, k, l, st_odd.n)
        else:
            ret = st_even.query(a, b, k, l, st_even.n)
    return ret

class Item():
    def __init__(self, mini, left, right):
        self.mini = mini
        self.left = left
        self.right = right

if __name__ == '__main__':
    n = int(input())
    arr = list(map(int, input().split(" ")))
    st_even = SegmentTree(n)
    st_odd = SegmentTree(n)
    h = dict()
    for i in range(n):
        h[arr[i]] = i
        if i % 2 == 0:
            st_even.update(i, arr[i])
        else:
            st_odd.update(i, arr[i])
    q = []
    hq = []
    x = wrap_query("even", 0, n, 0, 0)
    heapq.heappush(hq, (x, Item(h[x], 0, n)))

    while len(hq) != 0:
        q0, item = heapq.heappop(hq)
        l = item.left
        r = item.right
        i = item.mini
        q.append(q0)
        q1 = wrap_query("odd", i, r, 0, 0)
        j = h[q1]
        q.append(q1)
        if i - l > 1:
            x0 = wrap_query("even", l, i, 0, 0)
            heapq.heappush(hq, (x0, Item(h[x0], l, i)))
        if j - (i+1) > 1:
            x1 = wrap_query("even", i+1, j, 0, 0)
            heapq.heappush(hq, (x1, Item(h[x1], i+1, j)))
        if r - (j + 1) > 1:
            x2 = wrap_query("even", j+1, r, 0, 0)
            heapq.heappush(hq, (x2, Item(h[x2], j+1, r)))
    print(*q, sep=" ")

Submission status: Time Limit Exceeded

Solution code:
import heapq

MAX_N = 1 << 17
INT_MAX = 2**31 - 1

class SegmentTree():
    def __init__(self, n_):
        self.n = 1
        while self.n < n_:
            self.n *= 2
        self.dat = [INT_MAX] * (2 * self.n - 1)

    def update(self, k, a):
        k += self.n - 1
        self.dat[k] = a
        while k > 0:
            k = int((k - 1) / 2)
            self.dat[k] = min(self.dat[k * 2 + 1], self.dat[k * 2 + 2])

    def query(self, a, b, k, l, r):
        if (r <= a) or (b <= l):
            return INT_MAX
        if (a <= l) and (r <= b):
            return self.dat[k]
        else:
            vl = self.query(a, b, k * 2 + 1, l, (l + r) / 2)
            vr = self.query(a, b, k * 2 + 2, (l + r) / 2, r)
            return min([vl, vr])

def wrap_query(type, a, b, k, l, r):
    if type == "even":
        if a % 2 == 0:
            ret = st_even.query(a, b, k, l, r)
        else:
            ret = st_odd.query(a, b, k, l, r)
    else:
        if a % 2 == 0:
            ret = st_odd.query(a, b, k, l, r)
        else:
            ret = st_even.query(a, b, k, l, r)
    return ret

class Item():
    def __init__(self, mini, left, right):
        self.mini = mini
        self.left = left
        self.right = right

if __name__ == '__main__':
    n = int(input())
    arr = list(map(int, input().split(" ")))
    st_even = SegmentTree(n)
    st_odd = SegmentTree(n)
    h = dict()
    for i in range(n):
        h[arr[i]] = i
        if i % 2 == 0:
            st_even.update(i, arr[i])
        else:
            st_odd.update(i, arr[i])
    q = []
    hq = []
    x = wrap_query("even", 0, n, 0, 0, n)
    heapq.heappush(hq, (x, Item(h[x], 0, n)))

    while len(hq) != 0:
        q0, item = heapq.heappop(hq)
        l = item.left
        r = item.right
        i = item.mini
        q.append(q0)
        q1 = wrap_query("odd", i, r, 0, 0, n)
        j = h[q1]
        q.append(q1)
        if i - l > 1:
            x0 = wrap_query("even", l, i, 0, 0, n)
            heapq.heappush(hq, (x0, Item(h[x0], l, i)))
        if j - (i+1) > 1:
            x1 = wrap_query("even", i+1, j, 0, 0, n)
            heapq.heappush(hq, (x1, Item(h[x1], i+1, j)))
        if r - (j + 1) > 1:
            x2 = wrap_query("even", j+1, r, 0, 0, n)
            heapq.heappush(hq, (x2, Item(h[x2], j+1, r)))
    print(" ".join(map(str, q)))

Submission status: Time Limit Exceeded

Solution code:
import heapq

MAX_N = 1 << 17
INT_MAX = 2**31 - 1

class SegmentTree():
    max_n = 1 << 17
    int_max = 2**31 - 1
    def __init__(self, n_):
        self.n = 1
        while self.n < n_:
            self.n *= 2
        self.dat = [INT_MAX] * (2 * self.n - 1)
        self.dati = dict()

    def update(self, k, a):
        self.dati[a] = k
        k += self.n - 1
        self.dat[k] = a
        while k > 0:
            k = int((k - 1) / 2)
            self.dat[k] = min(self.dat[k * 2 + 1], self.dat[k * 2 + 2])

    def query(self, a, b, k, l, r):
        if (r <= a) or (b <= l):
            return INT_MAX
        if (a <= l) and (r <= b):
            return self.dat[k]
        else:
            vl = self.query(a, b, k * 2 + 1, l, (l + r) / 2)
            vr = self.query(a, b, k * 2 + 2, (l + r) / 2, r)
            return min([vl, vr])

def wrap_query(type, a, b, k, l, r):
    if type == "even":
        if a % 2 == 0:
            ret = st_even.query(a, b, k, l, r)
        else:
            ret = st_odd.query(a, b, k, l, r)
    else:
        if a % 2 == 0:
            ret = st_odd.query(a, b, k, l, r)
        else:
            ret = st_even.query(a, b, k, l, r)
    return ret

class Item():
    def __init__(self, mini, left, right):
        self.mini = mini
        self.left = left
        self.right = right

if __name__ == '__main__':
    n = int(input())
    arr = list(map(int, input().split(" ")))
    st_even = SegmentTree(n)
    st_odd = SegmentTree(n)
    h = dict()
    for i in range(n):
        h[arr[i]] = i
        if i % 2 == 0:
            st_even.update(i, arr[i])
        else:
            st_odd.update(i, arr[i])
    q = []
    hq = []
    x = wrap_query("even", 0, n, 0, 0, n)
    heapq.heappush(hq, (x, Item(h[x], 0, n)))

    while len(hq) != 0:
        v, item = heapq.heappop(hq)
        l = item.left
        r = item.right
        q0, i = v, item.mini
        q.append(q0)
        q1 = wrap_query("odd", i, r, 0, 0, n)
        j = h[q1]
        x0 = wrap_query("even", l, i, 0, 0, n)
        x1 = wrap_query("even", i+1, j, 0, 0, n)
        x2 = wrap_query("even", j+1, r, 0, 0, n)
        q.append(q1)

        if x0 != INT_MAX:
            heapq.heappush(hq, (x0, Item(h[x0], l, i)))
        if x1 != INT_MAX:
            heapq.heappush(hq, (x1, Item(h[x1], i+1, j)))
        if x2 != INT_MAX:
            heapq.heappush(hq, (x2, Item(h[x2], j+1, r)))
    print(" ".join(map(str, q)))

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq

# sys.stdin = open('e1.in')
 

def read_int_list():
    return list(map(int, input().split()))


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


def query(h, p, start, stop):
    if stop - start <= 2:
        return h[(start, stop)]
    else:
        l = 2
        while start + 2 * l < stop:
            l *= 2
        i, u = h[(start, start + l)]
        shift = 0
        if start % 2 != (stop - l) % 2:
            shift = 1
        start0 = stop - l + shift
        stop0 = stop + shift
        j, v = h[(start0, stop0)]
        if u < v:
            return i, u
        return j, v


def solve():
    inf = 10 ** 20
    n = read_int()
    p = read_int_list()

    h = {}
    for i in range(0, n):
        h[(i, i + 1)] = i, p[i]
        h[(i, i + 2)] = i, p[i]

    l = 2
    while 2 * l <= n:
        for i in range(0, n - 2 * l + 2):
            j, u = h[(i, i + l)]
            k, v = h[(i + l, i + 2 * l)]
            if u < v:
                h[(i, i + 2 * l)] = j, u
            else:
                h[(i, i + 2 * l)] = k, v
        l *= 2

    q = []
    i, u = query(h, p, 0, n)
    j, v = query(h, p, i + 1, n)

    heapq.heappush(q, (u, v, i, j, 0, n))
    res = []
    for step in range(n // 2):
        u, v, i, j, start, stop = heapq.heappop(q)
        if start < i:
            k, x = query(h, p, start, i)
            l, y = query(h, p, k + 1, i)
            heapq.heappush(q, (x, y, k, l, start, i))
        if i + 1 < j:
            k, x = query(h, p, i + 1, j)
            l, y = query(h, p, k + 1, j)
            heapq.heappush(q, (x, y, k, l, i + 1, j))
        if j + 1 < stop:
            k, x = query(h, p, j + 1, stop)
            l, y = query(h, p, k + 1, stop)
            heapq.heappush(q, (x, y, k, l, j + 1, stop))
        res.append((u, v))
    return res


def main():
    res = solve()
    for pair in res:
        print(*pair, end=' ')
    print()


if __name__ == '__main__':
    main()