Solução Informática Avançado - Semana 70

Solução por Samyra Almeida

Conhecimentos prévios necessários:

Decomposição em raiz

Dividiremos o vetor em $\sqrt{N}$ blocos de tamanho $\sqrt{N}$ . Com isso chamaremos de $qtd[i]$ é o igual a quantidade de pulos do buraco $i$ até a primeira posição fora do bloco de $i$ , $ultimo[i]$ é a ultima posição, do mesmo bloco de $i$ , que a bola pula se fosse jogada na posição $i$ , $prox[i]$ é a próxima posição que a bola pula se for jogada na posição $i$ e o vetor v[] guarda o poder de cada buraco.

Antes de lermos os queries, iremos montar os vetores. Para o $i$ -ésimo buraco iremos fazer:

Vamos percorrer todos os buracos $j$ que estão entre $i$ e o inicio de seu bloco, a partir dai iremos anualizar três possíveis casos:

Para evitar possíveis duvidas, $v[j] =$ poder do buraco $j$ e $j$ é o buraco que eu estou, logo $v[j] + j$ a posição que eu irei após cair no $j$ -ésimo buraco. Com isso, vamos analisar os casos =D!

Caso $v[j] + j data-recalc-dims=$ n" />: Nesse caso a bola irá sair do vetor. Portanto:
- $qtd[j] = 1$
- $ultimo[j] = j$
- $prox[j] = v[j] + j$
Caso $v[j] + j < fim$ , sendo $fim$ $=$ $final$ $do$ $bloco$ $de$ $j + 1$ : Nesse caso a bola irá sair do vetor. Portanto:
- $qtd[j] = qtd[v[j] + j] + 1$ , a quantidade de pulos que v[j] + j leva até o final do bloco mais $1$ , ou seja, meu pulo até $v[j] + j$ .
- $ultimo[j] = ultimo[v[j] + j]$ , ultima posição que $j$ pula dentro do bloco é a mesma de $v[j] + j$
- $prox[j] = v[j] + j$ , a próxima posição é $v[j] + j$
Caso $v[j] + j$ está entre $fim$ e $n$ : Nesse caso o próximo pulo será para fora do bloco de $j$ , então faremos:
- $qtd[j] = 1$
- $ultimo[j] = j$
- $prox[j] = v[j] + j$

Bem, após tudo isso, iremos ler e processar as queries:

Para as queries do tipo $0$ $a$ $b$ , perceba que só precisamos atualizar o bloco em $a$ pertence pois como nós só calculamos a quantidade de pulos necessários para sair de um buraco até o final de seu bloco a alteração na potencia do $a$ -ésimo buraco só interfere no seu próprio bloco. Para isso, iremos fazer as mesmas operações que fizemos para construir os vetores, $qtd[]$ , $ultimo[]$ e $prox[]$ , porem, somente para os buracos de $a$ até o inicio de seu bloco.

E para as queries do tipo $1$ $a$ iremos criar duas variáveis, $pulos$ , que no inicio é $0$ , e $x$ , que no inicio é $a$ , e faremos um $while(true)$ onde para cada iteração faremos:

$pulos +=$ $qtd[x]$ , somamos a quantidade de pulos ate sair do bloco que $x$ está.
$x = ultimo[x]$ , atualizamos a ultima posição.
Checamos se $prox[x] > n$ , ou seja, se o próximo pulo sai do vetor, se sim, paramos o loop, se não, fazemos pulamos para a próxima posição.

Ao final do loop, basta imprimir $x$ e $pulos$ .

Segue o código solução para maior compressão:

	// NOIC - Problemas da Semana 69 - Intermediário
	// Solução por Samyra Almeida

	#include <bits/stdc++.h>

	using namespace std;

	const int maxn = 1e5+10, root = 340; // declaro maxn e root como constantes,
	// observe que coloquei o root como 340 pq por alguma razao fica um pouquinho mais rapido quando n e no maximo 10^5
	// nos testamos em alguns juizes e ficou mais rapido, mas se quiser usar como 320 fique a vontade.

	int n, m;
	int v[maxn], qtd[maxn], ultimo[maxn], prox[maxn]; // declaro as variaveis e vetores que irei precisar

	void build()
	{
	for(int i = n ; i > 0 ; --i) // passo por todas as posiçoes do vetor, ou seja, por todos os buracos
	{
	int ini, fim;
	ini = i/root;
	fim = ini + 1;

	ini = root, fim = root; // calculo a primeira e a ultima posicao do bloco que i pertence
	// OBS: pode ficar um pouco confuso mas tente observar que na verdade a variavel fim guarda
	// a primeira posicao do proximo bloco, ou seja, o bloco de i abrange as posiçoes de ini ate fim - 1.

	for(int j = i ; j >= max(ini, 1) ; --j) // percorro da posiçao i ate o inicio do bloco de i
	{
	if(v[j] + j > n) // se o proximo pulo sai do vetor
	{
	qtd[j] = 1; // a quantidade de pulos para sair do vetor e 1
	ultimo[j] = j; // a ultima posiçao que eu pulei dentro do meu bloco foi a posiçao j
	}
	else if(v[j] + j < fim) // se o proximo pulo e dentro o meu bloco, seria a mesma coisa de testar v[j] + j <= fim - 1
	{
	qtd[j] = qtd[j + v[j]] + 1; // a quantidade de pulos ate o final do bloco e igual a quantidade de pulos que o meu proximo cara deu ate o final do bloco mais 1 (meu pulo ate v[j] + j)
	ultimo[j] = ultimo[j + v[j]]; // o ultimo de j e o mesmo que o de v[j] + j
	}
	else // se o meu proximo pulo for em alguma outra posiçao, ainda dentro do vetor mas fora do meu bloco
	{
	qtd[j] = 1; // a quantidade de pulos para sair do vetor e 1
	ultimo[j] = j; // a ultima posiçao que eu pulei dentro do meu bloco foi a posiçao j
	}

	prox[j] = j + v[j]; // atualizo a posiçao do proximo pulo de j
	}
	}
	}

	int main()
	{
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

	cin >> n >> m;

	for(int i = 1 ; i <= n ; ++i) cin >> v[i];

	build(); // monto os vetores qtd, ultimo e prox.

	for(int i = 0 ; i < m ; ++i) // processo todas as queries
	{
	int type, a;
	cin >> type >> a;

	if(type) // se for do tipo 1
	{
	int pulos = 0, x = a; // no inicio nao dei nenhum pulo e estou na posiçao a

	while(true) // enquanto eu preciso pular de bloco
	{
	pulos += qtd[x]; // somo a pulos a quantidade de pulos para sair da posicao x ate a ultima posiçao que eu vou pular em meu bloco
	x = ultimo[x]; // pulo ate a ultima posiçao que eu consigo em meu bloco

	if(prox[x] > n) break; // se o proximo pulo for sair do vetor, paro o loop

	x = prox[x]; // caso contrario, pulo para a proxima posicao
	}

	cout << x << " " << pulos << "\n"; // imprimo a resposta
	}
	else // se a query for do tipo 0
	{
	int b;
	cin >> b;

	v[a] = b; // atualizo a potencia do buraco a

	int ini, fim;

	ini = a/root;
	fim = ini + 1;

	ini = root, fim = root; // calculo a primeira e a ultima posicao do bloco que a pertence
	// OBS: pode ficar um pouco confuso mas tente observar que na verdade a variavel fim guarda
	//a primeira posicao do proximo bloco, ou seja, o bloco de a abrange as posiçoes de ini ate fim - 1.

	for(int j = a ; j >= max(ini, 1) ; --j) // percorro o bloco da posiçao a ate o inicio do bloco
	{
	if(v[j] + j > n) // se o proximo pulo sai do vetor
	{
	qtd[j] = 1; // a quantidade de pulos para sair do vetor e 1
	ultimo[j] = j; // a ultima posiçao que eu pulei dentro do meu bloco foi a posiçao j
	}
	else if(v[j] + j < fim) // se o proximo pulo e dentro o meu bloco, seria a mesma coisa de testar v[j] + j <= fim - 1
	{
	qtd[j] = qtd[j + v[j]] + 1; // a quantidade de pulos ate o final do bloco e igual a quantidade de pulos que o meu proximo cara deu ate o final do bloco mais 1 (meu pulo ate v[j] + j)
	ultimo[j] = ultimo[j + v[j]]; // o ultimo de j e o mesmo que o de v[j] + j
	}
	else // se o meu proximo pulo for em alguma outra posiçao, ainda dentro do vetor mas fora do meu bloco
	{
	qtd[j] = 1; // a quantidade de pulos para sair do vetor e 1
	ultimo[j] = j; // a ultima posiçao que eu pulei dentro do meu bloco foi a posiçao j
	}

	prox[j] = j + v[j]; // atualizo o proximo cara que eu irei pular.
	}
	}
	}
	}

view raw

noic-intermediario-s69.cpp

hosted with ❤ by GitHub