Fişierul intrare/ieşire:capsuni.in, capsuni.outSursăConcurs Infogim 2018 clasa a 6-a
AutorDaniel RusuAdăugată deptestPaul Diac ptest
Timp execuţie pe test1 secLimită de memorie4096 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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.

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.incapsuni.out
3 4 2
1 1
2 3
8

Explicaţie

Exemplul este reprezentat în desenele din enunţ.

Trebuie sa te autentifici pentru a trimite solutii. Click aici