Fişierul intrare/ieşire:aparate.in, aparate.outSursăJunior Challenge 2020
AutorTinca MateiAdăugată deJuniorChallenge2020Comisia JuniorChallenge2020
Timp execuţie pe test0.5 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Aparate

În timp ce lumea e în carantină, K0Kalaru 47 se întoarce în habitatul său (adică aici, la Junior Challenge). Nature is healing.

De când nu l-am mai văzut, acesta a trecut prin foarte multe peripeţii. După ce a câştigat bani de la ediţiile trecute de JBOI, primul lucru pe care l-a făcut a fost să joace la jocurile de noroc (şi i-a pierdut pe toţi). În timp ce el vă povesteşte cu exactitate ce a jucat, el vă provoacă să calculaţi chiar voi ce pierderi imense a avut acesta.

La început, el vă descrie aparatul la care a jucat. Acesta este o matrice cu N linii (numerotate de la 1 la N) şi M coloane (numerotate de la 1 la M) cu valori întregi. K0Kalaru 47 începe să vă povestească Q evenimente în ordine cronologică. Evenimentele sunt de următoarea formă:

  • "Loveşte violent butonul din mijloc (sau ecranul, sau aparatul, sau ce vrei)" - o sa îi zicem update - şi coloanele cu indicii l, l + 1, l + 2, ..., r se rotesc cu k valori în sus.
  • "Te umpli de nervi, deoarece 'ai avut ghinion' şi ai pierdut mult mai mult decât trebuia să pierzi" - o să îi zicem query - se luminează celulele de la coordonatele (k, l), (k, l + 1), (k, l + 2), ..., (k, r), şi pierzi o sumă de bani egală cu suma celulelor aprinse. Celulele nu rămân aprinse până la sfârşitul jocului. După această operaţie, acestea se sting la loc.

Ca să îi demonstrezi lui K0Kalaru 47 că ai fost atent la toată povestea lui, vrei să îi zici la fiecare operaţie de tip query câţi bani a pierdut.

Date de intrare

În fişierul de intrare aparate.in, pe prima linie se află numerele N, M şi Q cu semnificaţia din enunţ.
Pe următoarele N linii se află câte M numere reprezentând matricea iniţială.
Pe următoarele Q linii se vor afla 4 numere tip l r k separate prin câte un spaţiu ce semnifică câte un eveniment:

  • Dacă tip este 1, atunci evenimentul respectiv este un update şi coloanele cu indicii de la l până la r se rotesc în sus cu k valori în sus
  • Dacă tip este 2, atunci evenimentul respectiv este un query la care trebuie să raspundeţi cu suma elementelor de pe linia k si coloanele cu indicii de la l până la r

Date de ieşire

În fişierul de ieşire aparate.out se vor afla pe mai multe linii răspunsurile în ordine la toate operaţiile de query ale lui K0Kalaru 47.

Restricţii

  • 2 ≤ N
  • 2 ≤ M
  • N * M ≤ 100.000
  • Q ≤ 50.000
  • 1 ≤ l ≤ r ≤ M pentru fiecare eveniment
  • 1 ≤ k ≤ N pentru fiecare eveniment
  • 1 ≤ type ≤ 2 pentru fiecare eveniment
  • Elementele din matrice sunt valori de la 1 până la 1.000.000. A se observa că, deoarece valorile sunt pozitive, K0Kalaru 47 nu are pierderi 'negative', deci nu are cum să câştige vreodată bani.
  • Fie A[1][c], A[2][c], ..., A[N][c] elementele de pe coloana c. O rotaţie 'în sus' a coloanei respective cu o poziţie înseamnă că se elimină elementul A[1][N], toate celălalte elemente se mută în sus cu o poziţie, iar poziţia care se eliberează jos de tot va fi înlocuită cu elementul care a fost eliminat. Astfel elementele coloanei o să fie (în ordine de sus în jos) A[2][c], A[3][c], ..., A[N][c], A[1][c].
  • O rotaţie în sus cu k poziţii a unei coloane înseamnă că rotim coloana respectivă cu o pozitie în sus de k ori.
  • K0Kalaru 47 nu recomandă absolut nimănui experienţa sa.

Subtaskuri

  • Subtaskul 1 (10 puncte, testele 1-2): Q ≤ 1.000
  • Subtaskul 2 (20 puncte, testele 3-6): M ≤ 1.000
  • Subtaskul 3 (30 puncte, testele 7-12): N = 2
  • Subtaskul 4 (40 puncte, testele 13-20): Restricţiile iniţiale

Exemplu

aparate.inaparate.out
4 6 5
1 3 5 2 6 7
3 4 9 2 1 9
1 1 1 1 1 1
9 9 7 7 7 9
1 3 5 2
1 2 5 3
2 4 6 1
2 3 5 2
2 1 6 3
10
3
27

Explicaţie

Iniţial, matricea arată astfel:
1 3 5 2 6 7
3 4 9 2 1 9
1 1 1 1 1 1
9 9 7 7 7 9

După prima operaţie, ea va arăta astfel:
1 3 1 1 1 7
3 4 7 7 7 9
1 1 5 2 6 1
9 9 9 2 1 9

După a doua operaţie, ea va arăta astfel:
1 9 9 2 1 7
3 3 1 1 1 9
1 4 7 7 7 1
9 1 5 2 6 9

Răspunsul la a treia operaţie va fi 2 + 1 + 7 = 10.
Răspunsul la a patra operaţie va fi 1 + 1 + 1 = 3.
Răspunsul la a cincea operaţie va fi 1 + 4 + 7 + 7 + 7 + 1 = 27.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?