noic-intermediario-s69.cpp

// 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.
			}		
		}
	}
}