Fişierul intrare/ieşire:ants.in, ants.outSursăConcurs Shumen seniori 2014
AutorGeorgi Georgiev, Yordan ChaparovAdăugată deteoionescuIonescu Teodor teoionescu
Timp execuţie pe test1 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Ants

Ţara furnicilor continuă să se extindă. Extinderea se face în următorul mod: când un oraş de furnici este suprapopulat, un număr de locuitori ai săi pleacă şi întemeiază un nou oraş (de fiecare dată când furnicile se mută, vor rămâne câteva şi în oraşul vechi). Iniţial, ţara furnicilor are un singur oraş. Din timpuri străvechi, furnicile au stabilit că în fiecare oraş vor fi exact M muşuroaie, numerotate cu întregi de la 1 la M, şi pentru fiecare muşuroi ştim câte furnici locuiesc în el. Când se întemeiază un nou oraş, M muşuroaie se construiesc imediat. Pentru că furnicile îşi respectă tradiţiile, ele au o înclinaţie naturală să îşi construiască muşuroaiele în oraşul nou într-un mod care seamănă cu muşuroaiele din oraşul din care s-au mutat. Adică, muşuroiul 1 din noul oraş va avea aceeaşi capacitate ca muşuroiul 1 din vechiul oraş, muşuroiul 2 din noul oraş - la fel ca muşuroiul 2 din vechiul oraş etc. Pe de altă parte, există furnici inovatoare care vor să facă anumite schimbări în planul noului oraş. Decizia, care a fost deja luată, este că la momentul întemeierii noului oraş, căpetenia furnicilor să dea ordin ca toate capacităţile musuroaielor numerotate de la L la R inclusiv, să fie mărite cu aceeaşi valoare V.
După ce au fost construite muşuroaiele din noul oraş, considerăm "cartierul select” al oraşului acele muşuroaie numerotate de la i la j inclusiv. Acum, căpetenia furnicilor se întreabă câte furnici pot fi găzduite în cartierul select din oraşul nou.
Scrieţi un program care răspunde la această întrebare pe măsură ce noi oraşe se întemeiază.

Date de intrare

Pe prima linie din fişierul de intrare ants.in se găsesc doi întregi: N - numărul de oraşe din ţara furnicilor după ce toate oraşele noi au fost întemeiate şi M - numărul de muşuroaie din fiecare oraş.
Pe a două linie se găsesc M întregi A1, A2, A3, …, AM, unde Ai reprezintă capacitatea muşuroiului i din primul oraş al ţării furnicilor.
Pe următoarele N-1 linii se găsesc câte şase întregi P, X, Y, V, Z, T care descriu parametrii folosiţi în momentul în care creăm un nou oraş. P reprezintă indicele oraşului din care se va forma un oraş nou. Indicele oraşului iniţial este 1. Fiecărui nou oraş întemeiat îi vom asocia un indice egal cu cel mai mic întreg pozitiv care nu a fost folosit ca indice pentru un oraş deja construit. Numerele L, R, i, j din enunţ sunt generate astfel:
L = ((X+S) mod M) + 1
R = ((Y+S) mod M) + 1
i = ((Z+S) mod M) + 1
j = ((T+S) mod M) + 1
Unde S este iniţial 0, iar după construirea unui oraş nou, valoarea lui S va fi actualizată astfel încât să fie egală cu numărul de furnici care pot locui în cartierul select al celui mai recent oraş nou construit, constând din toate muşuroaiele cu indici între i şi j inclusiv. Această valoare va fi folosită la calcularea parametrilor pentru construcţia următorului oraş (următorul din lista din input). Se garantează că L ≤ R şi i ≤ j pentru fiecare oraş.

Date de ieşire

Pentru fiecare oraş nou construit, afişaţi în fişierul ants.out câte un întreg pe o linie: S – numărul de furnici care pot locui în cartierul select al acelui oraş.

Restricţii

1 ≤ N ≤ 50000
1 ≤ M ≤ 100000
0 ≤ Ai, V ≤ 100000 pentru orice i între 1 şi M, şi orice V al fiecărui oraş nou construit
1 ≤ L ≤ R ≤ M pentru fiecare oraş nou construit
1 ≤ i ≤ j ≤ M pentru fiecare oraş nou construit
0 ≤ X, Y, Z, T < M
Pentru l0% din punctaj, N, M ≤ 1000.
Pentru 30% din punctaj, pentru fiecare oraş nou construit, P va fi egal cu indicele oraşului care a fost întemeiat exact înaintea oraşului curent.

Exemplu

ants.inants.out
4 4
3 6 7 5
1 2 3 1 0 1
2 1 2 6 2 2
1 0 2 8 0 3
9
12
45

Explicaţie

După toate operaţiile, vom avea 4 oraşe. În fiecare oraş vom avea 4 muşuroaie.
Muşuroaiele din oraşul 1 au capacităţile {3, 6, 7, 5}. Când creăm oraşul cu numărul 2, S = 0, L = 3, R = 4, i = 1, j = 2, V = 1. Capacităţile musuroaielor din oraşul 2 vor fi deci {3, 6, 8, 6} şi numărul de furnici care pot locui în cartierul select este 3 + 6 = 9. Setăm S = 9 înainte să construim noul oraş.
La momentul creării oraşului 3, S = 9. Se calculează L = ((1 + 9) mod 4) + 1 = 3, R = 4, i = ((2 + 9) mod 4) + 1 = 4, j = 4, V = 6. Cum oraşul 3 s-a format în urma suprapopulării oraşului 2, furnicile vor încerca să păstreze capacităţile din oraşul 2 cu schimbări minore. Capacităţile din oraşul 3 sunt {3, 6, 14, l2}. Cartierul select este format doar din muşuroiul 4 care are capacitatea 12. Setăm S = 12 înaintea trecerii la oraşul 4.
Oraşul 4 se construieşte în urma suprapopulării oraşului 1. Cu noua valoare a lui S calculăm L = 1, R = 3, i = 1, j = 4, V = 8. Capacităţile sunt {11, 14, 15, 5}. Toate muşuroaiele sunt în cartierul select: 11 + 14 + 15 + 5 = 45.

Trebuie sa te autentifici pentru a trimite solutii. Click aici