Fişierul intrare/ieşire:numerex.in, numerex.outSursăAlgoritmiada 2011, Runda 3
AutorAndrei Parvu, Bogdan-Cristian Tataroiu, Tiberiu SavinAdăugată dedevilkindSavin Tiberiu devilkind
Timp execuţie pe test1.5 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

NumereX

Se consideră un vector cu N numere, iniţial egale cu 0, asupra căruia se vor efectua M operaţii astfel:

  • UPDATE x l k: Pentru orice i, x <= i <= x + l - 1, valoarea elementului i din vector creşte cu k * (i - x + 1). Practic primul element din interval creşte cu valoarea k, al doilea cu 2 * k şi aşa mai departe până la ultimul element.
  • QUERY x y: Se cere să se spună care este suma elementelor de pe intervalul [x, y].

Cerinţă

Dându-se N, M şi cele M operaţii, trebuie să scrieţi un program care să efectueze aceste operaţii într-un mod cât mai eficient şi să scrie în fişierul de ieşire răspunsurile pentru operaţiile de tip QUERY.

Date de intrare

Fişierul de intrare numerex.in va conţine pe prima linie numerele N şi M. Pe următoarele M linii vor fi descrise operaţiile. Fiecare linie care descrie o operaţie începe cu un cod binar (un număr întreg cu valoarea 0 sau 1) şi continuă cu 2 sau 3 numere întregi:

  • Un cod 0 va semnifica o operaţie de UPDATE şi va fi urmat de 3 numere x, l şi k (cu semnificaţia din enunţ)
  • Un cod 1 va semnifica o operaţie de QUERY şi va fi urmat de 2 numere x şi y (cu semnificaţia din enunţ)

Date de ieşire

În fişierul de ieşire numerex.out se vor scrie pe câte o linie sumele cerute de fiecare operaţie de tip QUERY (sumele se cer în ordinea apariţiei operaţiilor în fişierul de intrare).

Restricţii

  • 1 ≤ N ≤ 100 000
  • 1 ≤ M ≤ 200 000
  • Pentru toate operaţiile de tip UPDATE puteţi considera 1k100 000
  • Pentru toate operaţiile de tip QUERY răspunsul va fi mai mic decât 264

Exemplu

numerex.innumerex.out
4 4
0 1 3 2
1 2 4
0 2 3 3
1 1 3
10
21

Explicaţie

După prima operaţie de UPDATE vectorul va fi 2 4 6 0, iar suma pe intervalul [2, 4] este egală cu 10.
După a doua operaţie de UPDATE vectorul va fi 2 7 12 9 iar suma pe intervalul [1, 3] este egală cu 21.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content