1/3

InternationalOlympiadinInformatics201526thJuly-2ndAugust2015Almaty,KazakhstanDay2

horsesLanguage:ro-RO

HorsesLuiMansurîiplacesăcreascăcaiurmândtradițiastrămoșilorsăi.ElareacumcemaimarehergheliedinKazakhstan.Nuașastăteaulucrurilecu aniînurmă.CândMansureradoarundzhigit(cuvântulKazakhpentrutânăr)elaveadoarunsingurcal.Elvisasăfacăogrămadădebanișiînceledinurmăsăajungăunbai(cuvântulkazakhpentruomfoartebogat).

Sănumerotămaniidela la înordinecronologică(adicăanul estecelmairecentan).Climadinfiecareaninfluențacreștereahergheliei.Pentrufiecarean Mansurmemoreazăuncoeficientdecreștereîntregșipozitiv .Dacălaînceputulanului aveai caiatuncilasfârșitulacestuiaaveai caiînherghelie.

Caiiputeaufivânduținumailasfârșitulunuian.Pentrufiecarean ,Mansurmemoreazăunîntregpozitiv :prețulunuicallasfârșitulanului .Lasfârșitulfiecăruianeraposibilsăvinzioricâțicai,fiecarelaacelasipreț .

Mansurseîntreabăcareesteceamaimaresumădebanipecarearputeasăoobținădacăalegecelemaibunemomenteîncaresăvândăcaipeparcursulcelor ani.TuaionoareasăfiiinvitaltulluiMansurîntoi(cuvântulkazakhpentruvacanță)șisărăspunzilaîntrebarealui.

MemorialuiMansurseîmbunătățeșteseara,așacavafaceunșirde modificări.Fiecaremodificarevaschimbafieunadintrevalorile ,fieunadintrevalorile .Dupăfiecaremodificareelteîntreabădinnoucareesumaceamaimarepecareopoateobținedinvânzareacailor.ModificărileluiManursuntcumulative:fiecarerăspunstrebuiesăținăcontdetoatemodificărileprecedente.Reținețicăoricaredintrevalorile sau arputeafimodificatădemaimulteori.

RăspunsulluiMansurpoatefiunnumărfoartemare.Pentruaevitalucrulcunumeremariseceredoarrestulmodulo alrăspunsului.

ExempluSăpresupunemcă ani,cuurmătoareleinformații:

0 1 2

X 2 1 3

Y 3 4 1

PentruvalorileinițialeMansurpoateobținecelmaimultdacăvindeambiisăicailasfârșitulanului1.Procesuldecurgedupăcumurmează:

Inițial,Mansurareuncal.

Dupăanul0elare cai.

2/3

Dupăanul1elare cai.

Elpoateacumsăvândăceidoicai.Profitultotalvafi .

Săpresupunemacumcăexistă modificări:Schimbăvaloarealui în .

Dupămodificareavem:

0 1 2

X 2 1 3

Y 3 2 1

Înacestcaz,unadintresoluțiileoptimeestesăvinziuncaldupăanul0șiapoitreicaidupăanul2.Procesuldecurgedupăcumurmează:

Inițial,Mansurareuncal.

Dupăanul0elare cai.

Elpoatesăvândăunuldintrecaipentru ,șiîimairămâneuncal.

Dupăanul1elare cal.

Dupăanul2elare cai.

Elpoateacumsăvândăceitreicaipentru .Profitultotalvafi .

CerințăSedau , , ,șilistademodificări.Înaintedeprimamodificareșidupăfiecaremodificare,calculeazăsumamaximăpecareopoateobțineMansurpecaiisăi,modulo .Trebuiesăimplementezifuncțiileinit,updateXșiupdateY.

init(N,X,Y)—Grader-ulvaapelaprimaaceastăfuncție,exactodată.

N:Număruldeani.

X:unșirdelungime .Pentru , dăcoeficientuldecreșterepentruanul .

Y:unșirdelungime .Pentru , dăprețulunuicaldupăanul .

RemarcațicăatâtXcâtșiYspecificăvalorileinițialedatedeMansur(înaintedeoricemodificare).

Dupăceapelulinitseîncheie,șirurileXșiYrămânvalabile,șipoțimodificaconținutullordupăcumdorești.

AceastăfuncțietrebuiesăreturnezesumamaximăpecareopoateobțineMansurpecaiisăipentruacestevaloriinițialealelui și ,modulo .

updateX(pos,val)pos:unîntregdinintervalul .

3/3

val:nouavaloarealui pos .

AceastăfuncțietrebuiesăreturnezesumamaximăpecareopoateobțineMansurdupăaceastămodificare,modulo .

updateY(pos,val)pos:unîntregdinintervalul .

val:nouavaloarealui pos .

AceastăfuncțietrebuiesăreturnezesumamaximăpecareopoateobțineMansurdupăaceastămodificare,modulo .

Seasigurăcăatâtvalorileinițialecâtșicelemodificatepentru șisuntîntre și inclusiv.Dupăinit,grader-ulvaapelaupdateXșiupdateYdecâtevaori.NumărultotaldeapelurialefuncțiilorupdateXșiupdateYvafi .

Subprobleme

Subproblema puncte Precizărisuplimentare

1 17 ,

2 17 none

3 20 și pentruinitșiapelurileupdateX

4 23 none5 23 none

Grader-uldepecalculatorultăuGrader-uldepecalculatorultăuciteștedatedeintraredinfișierulhorses.inînurmătorulformat:

linia1:Nlinia2:X[0]…X[N-1]linia3:Y[0]…Y[N-1]linia4:Mliniile5,…,M+4:treinumeretypeposval(type=1pentruupdateXșitype=2pentruupdateY).

Grader-uldepecalculatorultăuafișeazăvaloareareturnatădeapeluliniturmatădevalorilereturnatedetoateapelurileupdateXșiupdateY.