4088 - BSTQ

Se consideră un șir A, inițial vid. Asupra lui A se aplică n operații de două tipuri:

1 x – adaugă numărul x în A 2 k – dacă A ar fi ordonat crescător, care ar fi a k-a valoare?

Cerința

Să se răspundă la cele n întrebări.

Date de intrare

Fișierul de intrare bstqin.txt conține pe prima linie numărul n, iar pe următoarele n linii se află câte o operație de tip 1 sau 2.

Date de ieșire

Fișierul de ieșire bstqout.txt va conține atâtea linii câte operații de tip 2 sunt în fișierul de intrare.

Restricții și precizări

• 1 ≤ n ≤ 200.000
• Numerele care se adaugă în A sunt numere întregi reprezentate pe 32 de biți cu semn.
• Este garantat că la orice operație 2 k valoarea lui k este mai mică sau egală decât numărul de elemente din A.
• Este garantat că numerele care se introduc în A prin operația de tip 1 sunt generate aleator.

Exemplul 1:

bstqin.txt

16
1 7
1 9
1 3
1 7
2 3
2 2
1 10
1 2
2 4
2 5
1 5
2 3
1 8
1 10
1 4
1 3

bstqout.txt

Datele de intrare corespund restrictiilor impuse
7
7
7
9
5

Exemplul 2:

bstqin.txt

bstq

bstqout.txt

Datele de intrare nu corespund restrictiilor impuse

Explicație

La prima întrebare, 2 3, deja în A sunt valorile 3,7,7,9, deci a treia valoare este 7. La a doua întrebare, 2 2, A = 3,7,7,9, deci a doua valoare este 7. La a treia întrebare, 2 4, A = 2,3,7,7,9,10, deci a patra valoare este 7. La a patra întrebare, 2 5, A = 2,3,7,7,9,10, deci a cincea valoare este 9. La a cincea întrebare, 2 3, A = 2,3,5,7,7,9,10, deci a treia valoare este 5.

Rezolvare

from bisect import insort_left


def validare(nr_n, operatii):
    if nr_n > 200000:
        raise ValueError
    for operation in operatii:
        if operation[0] == 1 and (operation[1] < -2147483648 or operation[1] > 2147483647):
            raise ValueError
    file_out.write("Datele de intrare corespund restrictiilor impuse\n")


def process_operations(operatii, fisier_out):
    a = []
    for operation in operatii:
        if operation[0] == 1:
            insort_left(a, operation[1])
        elif operation[0] == 2:
            fisier_out.write(str(a[operation[1] - 1]) + '\n')


if __name__ == '__main__':
    file_in = open("bstqin.txt", "r")
    file_out = open("bstqout.txt", "w")
    try:
        n = int(file_in.readline())
        operations = [list(map(int, file_in.readline().split())) for _ in range(n)]
        validare(n, operations)
        process_operations(operations, file_out)
    except ValueError:
        file_out.write("Datele de intrare nu corespund restrictiilor impuse")
    except IndexError:
        file_out.write("Datele de intrare nu corespund restrictiilor impuse")