Fişierul intrare/ieşire:ninja.in, ninja.outSursăAlgoritmiada 2014, Runda 2
AutorAdrian BudauAdăugată defreak93Adrian Budau freak93
Timp execuţie pe test0.75 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Ninja

Ninja A şi Ninja B vor să comită un furt respectabil. Respectabil în sensul că ceilalţi membri ai comunităţii ninja ar fi oarecum impresionaţi, deoarece până acum Ninja A şi Ninja B au comis infracţiuni cu cifra de afaceri în jurul a 3 portocale şi o amendă RATB. De această dată, cei doi vor să jefuiască rezervele de aur ale Băncii Naţionale. Acestea se află într-o cameră dreptunghiulară de dimensiune M x N. Fiecare rând al acestei camere conţine exact o grămadă de aur. Grămezile conţin lingouri de aur. Un lingou de aur de lungime L se întinde pe L coloane ale matricei. O grămadă de aur de dimensiune X, unde X este un număr impar, situată pe intervalul de coloane [LEFT, RIGHT] este constituită dintr-un lingou de aur de lungime X deasupra căruia se află o grămadă de dimensiune X - 2, situată pe intervalul de coloane [LEFT + 1, RIGHT - 1]. În cazul în care dimensiunea grămezii este egală cu 1 atunci aceasta nu are niciun alt lingou deasupra sa.

Fiecare coloană a camerei este dotată cu o cameră de vedere. Camera situată pe coloana C supraveghează toate lingourile care se suprapun cu coloana C.
Ninja A şi Ninja B se întreabă câte lingouri de aur ar rămâne nesupravegheate dacă ar stinge toate camerele de supraveghere din intervalul de coloane [R, C]. Ei vă cer răspunsul pentru mai multe întrebări de acest gen.

Date de intrare

Fişierul de intrare ninja.in va conţine trei numere naturale N, M, K reprezentând numărul de coloane, numărul de linii ale camerei respectiv numărul de întrebări la care trebuie să răspundeţi. Următoarele M linii vor conţine câte două numere X Y reprezentând faptul că pe linia respectivă se află o grămadă de aur situată pe intervalul de coloane [X, Y]. Următoarele K linii vor conţine de-asemenea două numere A B reprezentând o întrebare de tipul "Câte lingouri rămân nesupravegheate dacă se închid toate camerele din intervalul de coloane [A, B]?".

Date de ieşire

În fişierul de ieşire ninja.out se vor afla K linii fiecare conţinând un număr natural care reprezintă răspunsul la întrebarea corespunzătoare.

Restricţii

  • 1 ≤ N, M, K ≤ 105
  • Atentie! M reprezintă numărul de linii al matricei.

Exemplu

ninja.inninja.out
5 5 5
2 4
1 3
1 5
3 3
4 4
1 5
1 3
1 4
3 5
5 5
9
5
8
4
0
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content