Fișierul intrare/ieșire capsuni.in, capsuni.out Sursă Concurs Infogim 2018 clasa a 6-a
Autor Daniel Rusu Adăugată de avatar ptest Hai la Olimpiada - Iasi Gimnaziu ptest
Timp de execuție pe test 1 sec Limită de memorie 4096 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Capsuni

Notă: valorile maxime pentru N și M au fost modificate de la 100000 la 500000 pentru a corespunde testelor originale. De asemenea limita de timp de executare a fost micșorată de la 3 secunde la o secundă.

Vali iubește torturile de ciocolată, de vanilie, însă nu le suportă pe cele de căpșuni. Acesta este alergic la căpșuni. Nu vreți să știți ce pățește Vali când mănâncă o căpșună. Nimeni nu vrea să știe.
Vali a primit de la dușmanul său Leinad cadou un tort dreptunghiular împărțit în N linii și M coloane ce conține în unele zone CĂPȘUNI. Vali dorește să mănânce tort folosindu-se de următorul algoritm: Cât timp există o linie pe care nu se află căpșuni, acesta taie felia formată din linia respectivă, o mănâncă și merge mai departe. Când nu mai există nicio linie care să nu conțină vreo căpșună, caută o coloană pe care nu se află nicio căpșună și mănâncă toate celulele rămase conținute în acea coloană, apoi caută altă coloană. Când nu mai există nicio coloană care să nu conțină căpșuni, atunci Vali îi trimite mesaj dușmanului său Leinad cu numărul de celule din tort pe care le-a mâncat.

{! problema/capsuni?imaginecapsuni.png!}

Din păcate, Vali n-a știut că și blatul din care era format tortul conținea căpșuni, așa că acesta vă roagă pe voi să îi trimiteți mesaj lui Leinad cu numărul de celule distincte pe care acesta ar fi trebuit să le mănânce! În schimbul ajutorului vostru, Vali vă oferă 100 de căpșuni!

Date de intrare

În fișierul de intrare capsuni.in se dau pe prima linie trei numere naturale N, M si K, unde N și M reprezintă dimensiunile tortului, iar K numărul de căpșuni. Pe următoarele K linii se află câte două numere x și y, cu semnificația că pe linia x și coloana y în tort se află o căpșună.

Date de ieșire

În fișierul de ieșire capsuni.out se află un singur număr, reprezentând numărul de celule din tort pe care Vali ar fi trebuit să le mănânce.

Restricții

  • 1 ≤ N, M ≤ 500.000
  • 0 ≤ K ≤ 1.000.000
  • 1 ≤ x ≤ N
  • 1 ≤ y ≤ M
  • Pentru 30% din teste N, M ≤ 1.000
  • Pentru 10% din teste K = 0
  • Vali este bine și sănătos acum!

Exemplu

capsuni.in capsuni.out
3 4 2
1 1
2 3
8

Explicație

Exemplul este reprezentat în desenele din enunț.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii