== include(page="template/taskheader" task_id="zlego") ==
Poveste şi cerinţă...
p<>. Recent, Bujorel a dat în mintea copiilor şi s-a apucat să se joace cu piese de _zlego_. El are o piesă formată din $N$ bucăţi numerotate de la $1$ la $N$, fiecare cu o înalţime şi un coeficient de frumuseţe date. Se defineşte un _zprefix_ ca fiind un şir format din una sau mai multe bucăţi consecutive care să înceapă cu piesa $1$. Scopul este să aleagă un _zprefix_, să găsească toate apariţiile acestuia în restul piesei şi să facă suma costurilor de frumuseţe ale acestor apariţii. Pentru o apariţie a _zprefixului_ ales care corespunde secvenţei formate din bucăţile numerotate de la $i$ la $j$ (înălţimea bucăţii $1$ este egală cu înălţimea bucăţii $i$, înălţimea bucăţii $2$ este egală cu înălţimea bucăţii $i+1$ etc.) costul său de frumuseţe este coeficientul de frumuseţe al ultimei bucăţi, adică al lui $j$.
p<>. Bujorel e curios ce se întamplă pentru orice _zprefix_ şi vrea să afişeze suma costurilor de frumuseţe ale tuturor apariţiilor fiecarui _zprefix_.
h2. Date de intrare
Fişierul de intrare $zlego.in$ ...
p<>. Pe prima linie a fisierului $zlego.in$ se află numarul de teste $T$. Fiecare test are următorul format: pe prima linie un număr natural $N$ reprezentând dimensiunea piesei de _zlego_, pe următoarea linie se află $N$ numere întregi, reprezentând înălţimile pieselor, despărţite prin câte un spaţiu, iar pe cea de-a treia linie se află tot $N$ numere întregi, despărţite prin câte un spaţiu, cel de-al $i$-lea număr reprezentând coeficientul de frumuseţe a celei de-a $i$-a piese.
h2. Date de ieşire
În fişierul de ieşire $zlego.out$ ...
p<>. Fişierul $zlego.out$ trebuie să conţină, pentru fiecare din cele $T$ teste, câte $N$ linii, cea de-a $i$-a linie reprezentând suma costurilor de frumuseţe ale apariţiilor zprefixului $[1, i]$.
h2. Restricţii
* $... ≤ ... ≤ ...$
h2. Exemplu
* $1 ≤ N ≤ 250 000$
* $1 ≤ T ≤ 3$
* Înalţimile şi coeficienţii de frumuseţe ale bucăţilor piesei se încadreaza pe $32$ de biti cu semn;
* Pentru $20%$ din teste $N ≤ 100$;
* Pentru $50%$ din teste $N ≤ 1000$;
* *Atenţie!*: Bujorel recomandă tipuri de date pe $64$ de biţi pentru afişarea rezultatului.
table(example). |_. zlego.in |_. zlego.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
h2. Exemplu
...
table(example). |_. zlego.in |_. zlego.out |_. Explicaţie |
| 2
3
1 2 1
2 2 2
10
1 1 2 1 1 1 1 2 1 1
1 2 3 4 5 6 7 8 9 10
| 4
2
2
44
30
11
13
15
6
7
8
9
10
| În cel de-al doilea test, pentru zprefixul [1, 1] obţinem suma costurilor de frumusete ale apariţiilor acestuia
44 = 1+2+4+5+6+7+9+10. Pentru [1, 2] avem 2+5+6+7+10, pentru [1, 3] avem 3+8, pentru [1, 4] avem 4+9, pentru [1, 5]
avem 5 + 10, pentru [1, 6] avem 6, pentru [1, 7] avem 7, pentru [1, 8] avem 8, pentru [1, 9] avem 9, iar pentru
[1, 10] avem 10.
|
== include(page="template/taskfooter" task_id="zlego") ==
