Fişierul intrare/ieşire:soparla.in, soparla.outSursăad-hoc
AutorAutor NecunoscutAdăugată dealexpetrescuAlexandru Petrescu alexpetrescu
Timp execuţie pe test0.5 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Șopârla (clasa a 9-a)

Marcel studiază comportamentul şopârlelor. El are N borcane în care pune ouă de şopârlă. Şopârlele sunt de M tipuri. Tipul i de şopârlă depune într-o zi câte un ou în borcanele de la Ai la Bi. Mai exact, şopârla de tipul i adaugă câte un ou în borcanele Ai, Ai+1, ..., Bi, unde Ai şi Bi se cunosc.

Marcel ştie că în fiecare din cele Q zile unele şopârle îşi vor depune ouăle, altele nu. Anume, în ziua j, şopârlele cu indicii Xj, Xj+1, ..., Yj îşi vor depune ouăle, după obiceiul fiecărei şopârle. El cunoaşte Xj şi Yj. Observăm că de-a lungul zilelor, unele şopârle pot depune ouă de mai multe ori sau niciodată.

Marcel e curios câte ouă se vor afla în fiecare borcan la finalul celor Q zile.

Date de intrare

Fişierul de intrare soparla.in conţine:

  • pe prima linie, numerele N (numărul de borcane), M (numărul de şopârle) şi Q (numărul de zile)
  • pe următoarele M linii, câte 2 numere Ai şi Bi, care delimitează intervalul borcanelor în care depune şopârla i ouă
  • pe următoarele Q linii, câte 2 numere Xj şi Yj, care delimitează intervalul şopârlelor care depun ouă în ziua j

Date de ieşire

În fişierul de ieşire soparla.out se vor afla N numere, fiecare număr pe câte o linie, al i-lea număr reprezentând numărul de ouă din borcanul i la finalul celor Q zile.

Restricţii

  • 1 ≤ N ≤ 100.000
  • 1 ≤ M ≤ 100.000
  • 1 ≤ Q ≤ 100.000
  • 1 ≤ AiBi ≤ N
  • 1 ≤ XjYj ≤ M

Punctare

  • pentru 20% din teste, cunoaştem că N ≤ 1000, M ≤ 1000, Q ≤ 1000
  • pentru alte 20% din teste, cunoaştem că M ≤ 1000 şi Q ≤ 1000
  • pentru alte 20% din teste, cunoaştem că Q ≤ 1000
  • pentru alte 20% din teste, cunoaştem că M ≤ 1000

Precizare

  • Iniţial borcanele sunt goale.

Exemplu

soparla.insoparla.out
4 4 4
1 2
3 4
1 4
2 4
1 4
2 4
2 3
1 3
6
8
10
10

Explicaţie

Sunt 4 borcane şi 4 şopârle care depun ouă vreme de 4 zile. În prima zi toate şopârlele vor depune ouă. Prima va depune în borcanele 1 şi 2, a doua în borcanele 3 şi 4, a treia în borcanele 1, 2, 3 şi 4, iar a patra în borcanele 2, 3 şi 4. Şirul numărului de ouă din fiecare borcan va arăta astfel: 2, 3, 3, 3.

În a doua zi, şopârlele 2, 3 şi 4 vor depune ouă. A doua şopârlă va depune în borcanele 3 şi 4, a treia în borcanele 1, 2, 3 şi 4, iar a patra în borcanele 2, 3, şi 4. Şirul numărului de ouă din fiecare borcan va arăta astfel: 3, 5, 6, 6.

În a treia zi, şopârlele 2 şi 3 vor depune ouă. A doua şopârlă va depune în borcanele 3 şi 4, iar a treia în borcanele 1, 2, 3 şi 4. Şirul numărului de ouă din fiecare borcan va arata astfel: 4, 6, 8, 8.

În a patra zi, şopârlele 1, 2 şi 3 vor depune ouă. Prima va depune În borcanele 1 şi 2, a doua în borcanele 3 şi 4 iar a treia în borcanele 1, 2, 3 şi 4. Şirul numărului de ouă din fiecare borcan va arăta astfel: 6, 8, 10, 10. Acesta este şirul final, care trebuie afişat.

Trebuie sa te autentifici pentru a trimite solutii. Click aici