Fişierul intrare/ieşire:sea2.in, sea2.outSursăLot 2004
AutorRadu BerindeAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test0.5 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Sea2

Pe mare va avea loc o mare batalie intre N vapoare. Vapoarele sunt considerate niste puncte si sunt date prin coordonatele lor carteziene x si y. Din motive greu de inteles, vapoarele nu pot ataca decat vapoarele care se afla la stanga si mai jos (mai exact, un vapor la pozitia x1, y1 poate ataca alt vapor la pozitia x2, y2 daca si numai daca x1 > x2 si y1 > y2). Pentru ca aceasta batalie are loc in zona Triunghiului Bermudelor, vapoarele apar (se teleporteaza) pe rand in zona bataliei. Vapoarele sunt numerotate 1, 2, ..., N in ordinea aparitiei lor. In momentul in care un vas apare, daca exista alt vas care a aparut deja si care poate sa il atace pe cel nou, vasul nou este distrus instantaneu. Daca nu, vasul cel nou ramane pe mare si distruge toate vasele pe care le poate ataca.

Cerinta

Dandu-se coordonatele la care apar pe rand vapoarele, sa se afle pentru fiecare vapor daca este distrus sau nu in momentul aparitiei sale si daca nu este distrus, sa se precizeze numarul total de vapoare ramase pe mare dupa aparitia sa.

Date de intrare

Pe prima linie a fisierului de intrare sea2.in se afla numarul natural N reprezentand numarul de vapoare ce vor aparea pe mare. Pe fiecare dintre urmatoarele N linii se afla cate o pereche de numere intregi separate printr-un spatiu, reprezentand coordonata x respectiv y a vaporului corespunzator liniei (mai exact, pe linia i sunt scrise coordonatele vaporului i-1, pentru orice i de la 2 la N+1).

Date de iesire

Fisierul de iesire sea2.out va contine N linii, fiecare linie cu un numar intreg. Pe linia i se va afla -1 daca vaporul i este distrus in momentul aparitiei, sau un numar intreg strict pozitiv reprezentand numarul de vapoare de pe mare dupa aparitia vaporului i in caz contrar.

Restrictii

  • 1 ≤ N ≤ 200 000
  • Coordonatele sunt numere intregi strict pozitive mai mici sau egale cu 260 000
  • Nu vor exista doua vase cu aceeasi coordonata x sau aceiasi coordonata y

Exemplu

sea2.insea2.out
5
4 1
8 6
7 5
3 4
9 3
1
1
-1
-1
2

Explicatie

Vaporul 1 ramane pe mare
Vaporul 2 ramane pe mare si distruge vaporul 1
Vaporul 3 este distrus de vaporul 2
Vaporul 4 este distrus de vaporul 2
Vaporul 5 ramane pe mare, impreuna cu vaporul 2

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content