.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » sea2

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
sea2


Timp maxim de execuţie / test:
1.6s
Memorie totala disponibilă / stivă:
16MB / 1MB

Pe mare va avea loc o mare bătălie între N vapoare. Vapoarele sunt considerate nişte puncte şi sunt date prin coordonatele lor carteziene x şi y. Din motive greu de înţeles, vapoarele nu pot ataca decât vapoarele care se află la stânga şi mai jos (mai exact, un vapor la poziţia x1, y1 poate ataca alt vapor la poziţia x2, y2 dacă şi numai dacă x1 > x2 şi y1 > y2). Pentru că această bătălie are loc în zona Triunghiului Bermudelor, vapoarele apar (se teleportează) pe rând în zona bătăliei. Vapoarele sunt numerotate 1, 2, ..., N în ordinea apariţiei lor. În momentul în care un vas apare, dacă există alt vas care a apărut deja şi care poate să îl atace pe cel nou, vasul nou este distrus instantaneu. Dacă nu, vasul cel nou rămâne pe mare şi distruge toate vasele pe care le poate ataca.

Cerinţă

Dându-se coordonatele la care apar pe rând vapoarele, să se afle pentru fiecare vapor dacă este distrus sau nu în momentul apariţiei sale şi dacă nu este distrus, să se precizeze numărul total de vapoare rămase pe mare după apariţia sa.

Date de intrare

Pe prima linie a fişierului de intrare sea2.in se află numărul natural N reprezentând numărul de vapoare ce vor apărea pe mare. Pe fiecare dintre următoarele N linii se află câte o pereche de numere întregi separate printr-un spaţiu, reprezentând coordonata x respectiv y a vaporului corespunzător liniei (mai exact, pe linia i sunt scrise coordonatele vaporului i-1, pentru orice i de la 2 la N+1).

Date de ieşire

Fişierul de ieşire sea2.out va conţine N linii, fiecare linie cu un număr întreg. Pe linia i se va afla -1 dacă vaporul i este distrus în momentul apariţiei, sau un număr întreg strict pozitiv reprezentând numărul de vapoare de pe mare după apariţia vaporului i în caz contrar.

Restricţii

1 ≤ N ≤ 200000 (două sute de mii)
• Coordonatele sunt numere întregi strict pozitive mai mici sau egale cu 260000
• Nu vor exista două vase cu aceeaşi coordonată x sau cu aceeaşi coordonată y.

Exemple

sea2.insea2.outExplicaţii
5 4 1 8 6 7 5 3 4 9 3 1 1 -1 -1 2 Vaporul 1 rămâne pe mare
Vaporul 2 rămâne pe mare şi distruge vaporul 1
Vaporul 3 este distrus de vaporul 2
Vaporul 4 este distrus de vaporul 2
Vaporul 5 rămâne pe mare, împreună cu vaporul 2

autor: Radu Berinde
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
surse trimise | ajutor