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 bstq.in 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 bstq.out 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. Exemplu: bstq.in

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 bstq.out

7 7 7 9 5 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.

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