Fişierul intrare/ieşire:points2.in, points2.outSursăShumen 2019 Juniori
AutorAdăugată deMatteoalexandruMatteo Verzotti Matteoalexandru
Timp execuţie pe test3 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Points2

Se dau N puncte in planul XOY cu coordonatele numere intregi. Un punct se numeste extern daca ambele conditii sunt indeplinite simultan:

1. Poate fi mutat oricat de mult la stanga sau la dreapta fara sa atinga un alt punct
2. Poate fi mutat oricat de mult in sus sau in jos fara sa atinga un alt punct.

Un punct se numeste intern daca acesta nu poate fi mutat oricat de mult nici la stanga/dreapta nici in sus/jos fara sa atinga un alt punct.

Scrieti un program care gaseste numarul de puncte externe si numarul de puncte interne din configuratia initiala si apoi executa operatii de doua tipuri: "adaugare punct" si "stergere punct". Dupa fiecare operatie se cere, din nou, numarul nou de puncte externe si numarul nou de puncte interne.

Date de intrare

Fişierul de intrare points2.in contine pe prima linie numarul N de puncte initial. Pe fiecare din urmatoarele N linii se afla doua numere intregi pozitive, separate printr-un spatiu, ce reprezinta coordonatele fiecarui punct. Pe linia N + 2 se afla un numar natural Q, ce reprezinta numarul de operatii care trebuie efectuate. Pe urmatoarele Q linii se afla 3 numere intregi pozitive: primul numar poate fi 1 - daca adaugam un punct sau 2 - daca stergem un punct. Urmatoarele doua numere constituie coordonatele punctului ce trebuie adaugat/sters.

Date de ieşire

În fişierul de ieşire points2.out se vor afla Q + 1 linii. Pe prima linie se va afla numarul initial de puncte externe si interne. Pe linia i + 1 se va afla numarul de puncte externe si interne dupa operatia i.

Restricţii

  • 0 < N ≤ 100.000
  • 0 < Q ≤ 100.000
  • 0 < coordonatele fiecarui punct ≤ 100.000
  • Se garanteaza ca la fiecare operatie de tipul 2, punctul ce trebuie sters se afla in plan.
  • Se garanteaza ca la fiecare moment nu vor exista 2 sau mai multe puncte cu aceleasi coordonate simultan in plan.
  • Pentru 40% din teste, Q ≤ 2000 si nu exista mai mult de 2000 de puncte simultan in plan.

Exemplu

points2.inpoints2.out
10
1 4
2 1
1 2
3 4
4 2
2 2
1 1
3 1
3 2
4 3
3
1 4 4
2 1 1
1 2 3
6 1
5 1
6 1
7 2

Explicatie

Setul initial de puncte este dat in figura de mai sus. Punctul intern este notat cu □, punctele externe sunt notate cu ▪, iar restul punctelor sunt notate cu o

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?