InternationalOlympiadinInformatics2015
26thJuly-2ndAugust2015
Almaty,Kazakhstan
horses
Day2
Language:en-PRT
Horses
Mansuradoracriarcavalos,talcomoosseusantigosancestraisfaziam.Eletemagoraamaior
manadadecavalosdoCazaquistão.Noentanto,estenãofoisempreocaso.Há anosatrás,
Mansureraapenasumdzhigit(cazaqueparaumhomemjovem)etinhaumúnicocavalo.Elesonhava
ganharmuitodinheiroefinalmentetornar-seumbai(cazaqueparaumhomemmuitorico).
Numeramososanosde a
porordemcronológica(i.e.,oano
éomaisrecente).A
meteorologiadecadaanoinfluenciouocrescimentodamanada.Paracadaano ,Mansurrecorda-se
deumcoeficientedecrescimento
,queéuminteiropositivo.Secomeçasseoano com
cavalos,entãoterminariaoanocom
cavalosnasuamanada.
Oscavalossópodiamservendidosnofinaldecadaano.Paracadaano ,Mansurrecorda-setambém
deuminteiropositivo
:opreçopeloqualelepodiavenderumcavalonofinaldoano .Nofinalde
cadaano,erapossívelvenderumnúmeroarbitráriodecavalos,cadaumaomesmopreço
.
Mansurquestiona-sequaléamaiorquantiadedinheiroqueelepoderiateragorasetivesseescolhido
osmelhoresmomentosparavenderosseuscavalosduranteosNanos.Vocêtemahonradeserum
convidadodoMansurnoseutoi(cazaqueparadiafestivo),eelepediu-lhepararesponderaesta
pergunta.
AmemóriadoMansurmelhoraaolongodanoite,eporissoelefazumasequênciade
atualizações.Cadaatualizaçãoirámudarapenasumdosvalores
ouumdosvalores
.Depois
decadaatualizaçãoelepergunta-lhenovamenteaquantiadedinheiroquepodiaterganhoaovender
osseuscavalos.AsatualizaçõesdoMansursãocumulativas:cadaumadassuasrespostasdeveter
emcontatodasasatualizaçõesanteriores.Notequeumúnico
ou
podeseratualizado
múltiplasvezes.
AsrespostasparaasquestõesdoMansurpodeserenormes.Paraevitartrabalharcomnúmeros
grandes,sótemdereportarasrespostasmódulo
.
Exemplo
Suponhaqueexistem
anos,comaseguinteinformação:
0 1 2
X 2 1 3
Y 3 4 1
Paraestesvaloresiniciais,Mansurpodeganharomáximosevenderambososseuscavalosnofinal
doano1.Todooprocessoiráparecer-secomoseguinte:
Inicialmente,Mansurtem1cavalo.
1/3
Depoisdoano0eleterá
cavalos.
Depoisdoano1eleterá
cavalos.
Elepodeagoravenderessesdoiscavalos.Olucrototalserá
Deseguida,suponhaqueexisteuma
.
atualização:mudarovalorde
para .
Depoisdestaatualização,teremos:
0 1 2
X 2 1 3
Y 3 2 1
Nestecaso,umadassoluçõesótimaévenderumcavalodepoisdoano0eentãotrêscavalosdepois
doano2.Todooprocessoiráparecer-secomoseguinte:
Inicialmente,Mansurtem1cavalo.
Depoisdoano0eleterá
cavalos.
Elepodeagoravenderumdosseuscavalospor
Depoisdoano1eleterá
cavalo.
Depoisdoano2eleterá
cavalos.
,eficaraindacomumcavalo.
Elepodeagoravenderessesdoiscavalospor
.
.Ototaldedinheiroserá
Tarefa
Sãodados , , eumalistadeatualizações.Antesdaprimeiraatualização,edepoisdecada
atualização,calculeamáximaquantiadedinheiroqueMansurpodereceberpelosseuscavalos,
módulo
.
init(N,X,Y)—Oavaliadoriráchamarestafunçãonoinícioeexatamenteumavez.
N:onúmerodeanos.
X:umvetor(array)detamanho .Para
coeficientedecrescimentoparaoano .
Y:umvetordetamanho
finaldoano .
.Para
,
,
contémovalordo
contémopreçodeumcavalono
NotequeambososvetoresXeYespecificamosvaloresiniciaisdadosporMansur(antes
dequalqueratualização).
Depoisdeinitterminar,osvetoresXeYpermanecemválidos,epodemodificarosseus
conteúdosseassimodesejar.
AfunçãodevedevolveramáximaquantiadedinheiroqueMansurpodeconseguirpara
estesvaloresiniciaisde e ,módulo
.
2/3
updateX(pos,val)
pos:uminteironointervalo
val:onovovalorde
.
pos .
AfunçãodevedevolveramáximaquantiadedinheiroqueoMansurpodeconseguir
depoisdestaatualização,módulo
.
updateY(pos,val)
pos:uminteironointervalo
val:onovovalorde
.
pos .
AfunçãodevedevolveramáximaquantiadedinheiroqueoMansurpodeconseguir
depoisdestaatualização,módulo
.
Podeassumirquetodososvaloresiniciais,bemcomoosvaloresatualizadosde
e
estão
entre e
inclusive.
Depoisdechamarinit,oavaliadoriráchamarupdateXeupdateYdiversasvezes.Onúmerototal
dechamadasaupdateXeupdateYserá .
Subtarefas
subtarefa pontos
1
17
2
17
3
20
4
5
23
23
restriçõesadicionais
,
nenhuma
e
parainite
updateXrespetivamente
nenhuma
nenhuma
Avaliadorexemplo
Oavaliadorexemplolêoinputapartirdeumficheirohorses.innoseguinteformato
linha1:N
linha2:X[0]…X[N-1]
linha3:Y[0]…Y[N-1]
linha4:M
linhas5,…,M+4:trêsnúmerostypeposval(type=1paraupdateXetype=2para
updateY).
Oavaliadorexemploescreveovalorderetornodeinit,seguidopelosvaloresderetornodetodasas
chamadasaupdateXeupdateY.
3/3