Fişierul intrare/ieşire:maxq.in, maxq.outSursăONI 2007, clasele 11-12
AutorDaniel PasailaAdăugată deDITzoneCAdrian Diaconu DITzoneC
Timp execuţie pe test0.5 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Maxq

Johnie a inceput sa se joace cu un vector de numere. El dispune initial de un vector V cu N numere intregi (numerotate de la 0 la N-1) si poate efectua urmatoarele operatii:

  • schimbarea elementului de pe pozitia p cu un alt numar intreg;
  • aflarea subsecventei de suma maxima din V inclusa intre indicii a si b;

Cerinta

Ajutati-l pe Johnie sa efectueze repede operatiile de mai sus.

Date de intrare

Fisierul maxq.in contine pe prima linie numarul N reprezentand dimensiunea vectorului. Pe urmatoarea linie se gasesc N elemente reprezentand valorile initiale ale vectorului. Urmatoarea linie contine M, reprezentand numarul de operatii. Pe fiecare dintre urmatoarele M linii sunt descrise cele M operatii in forma urmatoare:

  • 0 i p: numarul 0 de la inceput codifica faptul ca operatia curenta este una de schimbare; astfel elementul de pe pozitia i a vectorului se inlocuieste cu numarul intreg p;
  • 1 a b: numarul 1 de la inceput codifica faptul ca operatia curenta este o intrebare; astfel se cere sa se afle subsecventa de suma maxima din vector inclusa intre indicii a si b (a ≤ b);

Date de iesire

Fisierul maxq.out trebuie sa contina un numar de linii egal cu numarul de intrebari din fisierul de intrare. Pe linia i se cere sa se afiseze un singur numar reprezentand suma maxima ce se poate obtine in contextul intrebarii i din fisierul de intrare (i=1,2,...); in cazul in care vor exista doar subsecvente de suma negativa se va afisa 0.

Restrictii

  • 1 ≤ N ≤ 200 000;
  • 1 ≤ M ≤ 200 000;
  • toate elementele vectorului apartin intervalului [-100000, 100000];
  • definim o subsecventa ca fiind un sir de termeni consecutivi din vector, iar suma ei se obtine adunand elementele ce o compun;
  • exista cel putin o intrebare.
  • pentru 20% din teste se garanteaza N ≤ 5000

Exemplu

maxq.inmaxq.out
5
1 -10 4 -1 9
4
1 0 3
0 1 1
1 0 3
1 2 4
4
6
12

Explicatie

Pentru prima intrebare se alege subsecventa formata de elementul pe pozitia 2 din vector. Pentru a 2-a intrebare se aleg primele 3 elemente din vector (elementul de pe pozitia 1 a fost schimbat). Pentru a 3-a intrebare se aleg toate elementele din intervalul cerut.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content