Fişierul intrare/ieşire:	treap.in, treap.out	Sursă	Concursul National de Informatica "Adolescent Grigore Moisil" 17
Autor	Patrick Sava	Adăugată de	AGMInformatica •AGMinformatica
Timp execuţie pe test	0.2 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Treap

- Arbore (graf neorientat conex si aciclic) cu N noduri
- Arbore binar (fiecare nod are cel putin 0 fii si cel mult doi fii)
- Arbore inradacinat in nodul 1
- Cati subarbori exista cu proprietatea ca orice nod am alege din acel subarbore, nodul respectiv are prioritatea mai mare sau egala cu a fiilor sai si cheia acelui nod este mai mare sau egala cu a unuia dintre fii daca acel fiu exista si mai mica strict decat a celuilalt fiu daca acesta exista ?

Date de intrare

Fişierul de intrare treap.in ...

Date de ieşire

În fişierul de ieşire treap.out se va afisa un sir de N numere dupa cum urmeaza : al i-lea numar din sir va fi 1 daca subarborele inradacinat in nodul i are proprietatea de treap si 0 altfel. Numerele vor fi afisate cu spatii intre ele

Restricţii

1 <= N <= 150000
1 <= KEY <= 1.000.000.000
1 <= PRIO <= 1.000.000.000
Arborele se considera ca este inradacinat in nodul 1
La finalul fisierului de iesire este '\n', nu spatiu

Exemplu

table(example). |_. treap.in |_. treap.out |
| 3
1 2
1 3
5 5 7
100 9 1
|
0 1 1

|

Explicaţie

...

Cum se trimit solutii?