Fișierul intrare/ieșire	treap.in, treap.out	Sursă	ad-hoc
Autor	Cătălin Frâncu	Adăugată de	Cătălin Frâncu • Catalin.Francu
Timp de execuție pe test	0.15 sec	Limită de memorie	4096 KB
Scorul tău	N/A	Dificultate	3.75

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Treap (clasele 11 și 12)

Se dă o colecție de N perechi (cheie, prioritate). Toate cheile sunt numere naturale distincte și toate valorile sunt numere naturale distincte. Să se construiască un min-treap cu aceste perechi. Cu alte cuvinte, să se așeze perechile într-un arbore binar cu proprietățile:

• O parcurgere în inordine a arborelui returnează perechile în ordinea crescătoare a cheilor.
• Orice nod cu excepția rădăcinii are prioritatea strict mai mare decât a părintelui.

Date de intrare

Fișierul de intrare treap.in conține pe prima linie numărul N. Pe următoarele N linii sunt date câte două numere, respectiv cheia și prioritatea unei perechi.

Date de ieșire

În fișierul de ieșire treap.out se vor scrie N linii. Pe linia i se vor scrie două numere P_i $D_i, unde P_i este indicele părintelui în treap al perechii [$i], iar D_i este 0 sau 1 după cum perechea i este fiu stâng sau fiu drept. Pentru rădăcină se vor scrie numerele 0 0.

Restricții

• 1 ≤ N ≤ 50.000
• cheile și prioritățile au valori între 0 și 1.000.000
• perechile sunt numerotate de la 1 la N.

Exemplu

treap.in	treap.out	Explicație
7 5 23 8 5 11 65 1 10 7 4 9 73 2 7	7 1 5 1 2 1 7 0 0 0 3 0 5 0