SHARE
TWEET

Untitled

a guest Oct 21st, 2019 88 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // NOIC - Problemas da Semana 70 - Avançado
  2. // Solução por Samyra Almeida
  3.  
  4. #include <bits/stdc++.h>
  5.  
  6. using namespace std;
  7.  
  8. const int maxn = 1e5+10, root = 340; // declaro maxn e root como constantes,
  9. // observe que coloquei o root como 340 pq por alguma razao fica um pouquinho mais rapido quando n e no maximo 10^5
  10. // nos testamos em alguns juizes e ficou mais rapido, mas se quiser usar como 320 fique a vontade.
  11.  
  12. int n, m;
  13. int v[maxn], qtd[maxn], ultimo[maxn], prox[maxn]; // declaro as variaveis e vetores que irei precisar
  14.  
  15. void build()
  16. {
  17.     for(int i = n ; i > 0 ; --i) // passo por todas as posiçoes do vetor, ou seja, por todos os buracos
  18.     {
  19.         int ini, fim;
  20.         ini = i/root;
  21.         fim = ini + 1;
  22.  
  23.         ini *= root, fim *= root; // calculo a primeira e a ultima posicao do bloco que i pertence
  24.             // OBS: pode ficar um pouco confuso mas tente observar que na verdade a variavel fim guarda a primeira posicao
  25.             // do proximo bloco, ou seja, o bloco de i abrange as posiçoes de ini ate fim - 1.
  26.  
  27.         for(int j = i ; j >= max(ini, 1) ; --j) // percorro da posiçao i ate o inicio do bloco de i
  28.         {
  29.             if(v[j] + j > n) // se o proximo pulo sai do vetor
  30.             {
  31.                 qtd[j] = 1; // a quantidade de pulos para sair do vetor e 1
  32.                 ultimo[j] = j; // a ultima posiçao que eu pulei dentro do meu bloco foi a posiçao j
  33.             }
  34.             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
  35.             {
  36.                 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)
  37.                 ultimo[j] = ultimo[j + v[j]]; // o ultimo de j e o mesmo que o de v[j] + j
  38.             }
  39.             else // se o meu proximo pulo for em alguma outra posiçao, ainda dentro do vetor mas fora do meu bloco
  40.             {
  41.                 qtd[j] = 1; // a quantidade de pulos para sair do vetor e 1
  42.                 ultimo[j] = j; // a ultima posiçao que eu pulei dentro do meu bloco foi a posiçao j
  43.             }
  44.            
  45.             prox[j] = j + v[j]; // atualizo a posiçao do proximo pulo de j
  46.         }
  47.     }
  48. }
  49.  
  50. int main()
  51. {
  52.     ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  53.  
  54.     cin >> n >> m;
  55.  
  56.     for(int i = 1 ; i <= n ; ++i) cin >> v[i];
  57.  
  58.     build(); //  monto os vetores qtd, ultimo e prox.
  59.  
  60.     for(int i = 0 ; i < m ; ++i) // processo todas as queries
  61.     {
  62.         int type, a;
  63.         cin >> type >> a;
  64.  
  65.         if(type) // se for do tipo 1
  66.         {
  67.             int pulos = 0, x = a; // no inicio nao dei nenhum pulo e estou na posiçao a
  68.  
  69.             while(true) // enquanto eu preciso pular de bloco
  70.             {
  71.                 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
  72.                 x = ultimo[x]; // pulo ate a ultima posiçao que eu consigo em meu bloco
  73.                
  74.                 if(prox[x] > n) break; // se o proximo pulo for sair do vetor, paro o loop
  75.  
  76.                 x = prox[x]; // caso contrario, pulo para a proxima posicao
  77.             }
  78.  
  79.             cout << x << " " << pulos << "\n"; // imprimo a resposta
  80.         }
  81.         else // se a query for do tipo 0
  82.         {
  83.             int b;
  84.                     cin >> b;
  85.  
  86.             v[a] = b; // atualizo a potencia do buraco a
  87.  
  88.             int ini, fim;
  89.            
  90.             ini = a/root;
  91.             fim = ini + 1;
  92.  
  93.             ini *= root, fim *= root; // calculo a primeira e a ultima posicao do bloco que a pertence
  94.                     // OBS: pode ficar um pouco confuso mas tente observar que na verdade a variavel fim guarda a primeira posicao
  95.                     // do proximo bloco, ou seja, o bloco de a abrange as posiçoes de ini ate fim - 1.
  96.  
  97.             for(int j = a ; j >= max(ini, 1) ; --j) // percorro o bloco da posiçao a ate o inicio do bloco
  98.             {
  99.                 if(v[j] + j > n) // se o proximo pulo sai do vetor
  100.                 {
  101.                     qtd[j] = 1; // a quantidade de pulos para sair do vetor e 1
  102.                     ultimo[j] = j; // a ultima posiçao que eu pulei dentro do meu bloco foi a posiçao j
  103.                 }
  104.                 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
  105.                 {
  106.                     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)
  107.                     ultimo[j] = ultimo[j + v[j]]; // o ultimo de j e o mesmo que o de v[j] + j
  108.                 }
  109.                 else // se o meu proximo pulo for em alguma outra posiçao, ainda dentro do vetor mas fora do meu bloco
  110.                 {
  111.                     qtd[j] = 1; // a quantidade de pulos para sair do vetor e 1
  112.                     ultimo[j] = j; // a ultima posiçao que eu pulei dentro do meu bloco foi a posiçao j
  113.                 }
  114.  
  115.                 prox[j] = j + v[j]; // atualizo o proximo cara que eu irei pular.
  116.             }      
  117.         }
  118.     }
  119. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top