Diferențe pentru problema/capsuni între reviziile #2 si #7

capsuni

Capsuni (clasa a 6-a)

== include(page="template/taskheader" task_id="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!
h2. Date de intrare

h2. Restricții

* $1 ≤ N, M ≤ 100.000$

* $1 ≤ N, M ≤ 500.000$

* $0 ≤ K ≤ 1.000.000$
* $1 ≤ x ≤ N$
* $1 ≤ y ≤ M$