Sorting queries - MarisaOJ: Marisa Online Judge

Given an array of integers

$a$ consisting of

$n$ integers. You are given

$q$ queries of the following types: -

$0 l r$ : Sort the integers

$a_l, a_{l+1}, \dots, a_r$ in ascending order. -

$1 l r$ : Sort the integers

$a_l, a_{l+1}, \dots, a_r$ in descending order. After

$q$ queries, determine the value at position

$m$ in the array

$a$ . ### Input - The first line contains two integers

$n$ and

$q$ . - The next

$q$ lines each contain a query in the format described above. - The last line contains an integer

$m$ . ### Output - Print a single integer, the value at position

$m$ after

$q$ queries. ### Constraints -

$1 \leq n, q \leq 10^5$ . -

$1 \leq m, a_i \leq n$ . ### Example Input:

$5 3 1 5 4 2 3 0 2 4 1 3 5 0 1 4 2$

Output:

$2$

Topic

Binary search

Data structure

Rating

2100

Solution (0)

Solution