Fişierul intrare/ieşire:nebuni.in, nebuni.outSursăONI 2015 baraj gimnaziu
Autorprof. Emanuela CherchezAdăugată detgm000Tudor Mocioi tgm000
Timp execuţie pe test0.2 secLimită de memorie25600 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

Nebuni (baraj gimnaziu)

Pe o tablă de şah cu N linii şi N coloane sunt plasaţi M nebuni. După cum se ştie de la jocul de şah, nebunii atacă doar în diagonală.
O poziţie de pe tabla de şah este considerată sigură dacă nu este atacată de niciun nebun aflat pe tablă.

Cerinţa

Scrieţi un program care să determine numărul de poziţii sigure de pe tabla de şah.

Date de intrare

Fişierul de intrare nebuni.in conţine pe prima linie numerele naturale N M, separate prin spaţiu, cu semnificaţia din enunţ. Pe următoarele M linii sunt descrise poziţiile (linia şi coloana, separate prin spaţiu) celor M nebuni, câte un nebun pe o linie a fişierului.

Date de ieşire

Fişierul de ieşire nebuni.out va conţine o singură linie pe care va fi scris un număr natural reprezentând numărul de poziţii sigure de pe tabla de şah.

Restricţii

  • 1 ≤ N ≤ 1000000
  • 1 ≤ M < 16 500
  • Liniile şi coloanele sunt numerotate de la 1 la N.
  • Pentru 50% dintre teste N ≤ 300.
  • Pentru 60% dintre teste M ≤ 1000.

Exemplu

nebuni.innebuni.out
5 4
2 1
1 3
4 2
5 2
6

Explicaţie

Pe tabla de şah de dimensiune 5×5 se află 4 nebuni.
Poziţiile atacate de cei 4 nebuni sunt marcate cu gri.

Trebuie sa te autentifici pentru a trimite solutii. Click aici