Fişierul intrare/ieşire:undo.in, undo.outSursăLot Mehedinți 2015 - Baraj 5 Seniori
AutorAndrei Heidelbacher, Eugenie Daniel PosdarascuAdăugată deatatomirTatomir Alex atatomir
Timp execuţie pe test1 secLimită de memorie45056 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Undo

Bossanip vă dă o matrice N * N iniţial plină cu 0. Se pot executa asupra ei 3 tipuri de operaţii:

  • Update x y z: La valoarea elementului de pe linia x şi coloana y se adună valoarea întreagă z.
  • Query x y: Se cere suma elementelor din submatricea determinată de colţul stânga-sus (1,1) şi colţul dreapta-jos (x,y).
  • Undo x: Elimină ultimele x operaţii de Update şi Undo.

Se dau M astfel de operatii.

Date de intrare

Pe prima linie a fişierului de intrare undo.in se va afla un număr natural N şi un număr natural M. Pe următoarele M linii vor fi cele M operaţii ( 1 x y z pentru Update; 2 x y pentru Query; 3 x pentru Undo)

Date de ieşire

În fişierul de ieşire undo.out se va afisa răspunsul pentru fiecare operaţie de tip Query, câte unul pe linie.

Restricţii

  • 1 ≤ N ≤ 520
  • 1 ≤ M ≤ 500 000
  • Se garantează că la operatiile de tip Undo x au existat cel puţin x operatii de Update şi Undo înainte.
  • 1 ≤ z ≤ 2 000, pentru orice operaţie de tip 1
  • L-aţi uitat pe Tassadar!

Exemplu

undo.inundo.out
5 11
1 1 1 2
1 2 3 1
2 1 3
1 3 2 4
1 2 2 10
2 3 2
3 2
1 1 1 3
2 5 5
3 3
2 4 4
2
16
6
7
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?