Problem
Il pascolo del contadino John può essere rappresentato come un'enorme griglia 2D di celle (un'enorme scacchiera). Inizialmente, il pascolo è vuoto.
L'agricoltore John aggiungerà N (1≤N≤10
5) mucche al pascolo una per una. L'i-esima vacca occupa una cella (x
i,y
i) diversa dalle celle occupate da tutte le altre vacche (0≤x
i sub>, y
i≤1000).
Si dice che una mucca sia "comoda" se ha esattamente altre tre mucche orizzontalmente e verticalmente. L'agricoltore John vuole contare quante mucche stanno bene nel suo pascolo. Per ogni i nell'intervallo 1…N, stampa il numero totale di vacche che stanno bene dopo che l'i-esima vacca è stata aggiunta al pascolo.
Inserisci:
La prima riga contiene un singolo numero intero N. Ognuna delle seguenti N righe contiene due numeri interi separati da spazi che indicano le coordinate (x,y) della cella della mucca. È garantito che tutte le celle siano distinte.
Uscita:
La i-esima riga dell'output dovrebbe contenere il numero totale di vacche che si sentono a proprio agio dopo aver aggiunto l'i-esima vacca al pascolo.
Esempi
| # |
Input |
Uscita |
Spiegazione |
| 1 |
8
0 1
10
1 1
1 2
2 1
2 2
3 1
3 2 |
0
0
0
1
0
0
1
2 |
Dopo che le prime 4 vacche sono state aggiunte, la vacca nella cella (1,1) è a suo agio.
Dopo aver aggiunto le prime 7 vacche, la vacca nella cella (2,1) è a suo agio.
Dopo aver aggiunto le prime 8 vacche, la vacca nelle celle (2,1) e (2,2) è a suo agio. |