beecrowd asked 8 years ago

URI Online Judge Fórum 1.0

MOD

This topic was solved and cannot recieve new replies.

• 

  +4

  drangelp replied 7 years ago

  Gente, eu passei esse problema usando a implementação do livros dos Halim, mas ela passou com um tempo bem elevado, alguém poderia me dizer o motivo?

  Obrigado

  #include <bits/stdc++.h>
  
  using namespace std;
  
  class FenwickTree
  {
      private: vector <int> ft;
      public:
  
          FenwickTree (int n)
          {
              ft.assign (n + 1, 0);
          }
  
          int rsq (int b)
          {
              int sum = 0;
              for (; b; b -= b & (-b))
                  sum += ft[b];
              return sum;
          }   
  
          int rsq (int a, int b)
          {
              return rsq (b) - (a == 1 ? 0 : rsq (a - 1));
          }
  
          void att (int k, int v)
          {
              for (; k < (int) ft.size (); k += k & (-k))
                  ft[k] += v;
          }
  };
  
  int main ()
  {
      int n, bug;
      char c;
  
      cin >> n;
  
      FenwickTree ft (n + 1);
  
      for (int i = 1; i <= n; i++)
      {
          scanf ("%d", &bug);
          ft.att (i, bug);
      }
  
      while (cin >> c >> n && !cin.eof ())
      {
          if (c == 'a')
              ft.att (n, -ft.rsq (n, n)); // apago a posicao (n, n) <= pega o valor exato na posicao
          else
              printf ("%d\n", ft.rsq (1, n - 1)); // imprimo o valor de [1, n[
      }
  
      system ("pause");
      return 0;
  }

• 

  0

  griposati replied 7 years ago

  tá dando time limit e não consigo pensar noutra solução não alguma ajuda ? Obrigadão

  #include <stdlib.h>
  #include <stdio.h>
  
  int a[100000];
  int vet[100000];
  
  void update(int i,int value,int tamanhoVetor){ // complexidade O(log n)
  
      if(i > tamanhoVetor){
          return;
      }
  
      a[i] += value;
  
      i = i + (i & (-i));
  
      update(i,value,tamanhoVetor);
  }
  
  int get(int i){ // complexidade O(log n)
  
      int sum = 0;
  
      while(i > 0){
  
          sum += a[i];
  
          i = i - (i & (-i));
      }
  
      return sum;
  }
  
  int main()
  {
      int i = 0,v,abduzidoOuMostraValores;
      char charInformado;
  
      scanf("%d",&v);
  
      for(i=0;i<v;i++){
          scanf("%d",&vet[i]);
      }
  
      i=1;
      while(i <= v){ /// monta o vetor
          update(i,vet[i-1],v);
          i++;
      }
  
      while(scanf("%c %d",&charInformado,&abduzidoOuMostraValores)!=EOF){
  
          if(charInformado=='a'){
  
              for(i=0;i<=v;i++){
                  a[i] = 0;
              }
  
              vet[abduzidoOuMostraValores-1] = 0;
  
              i=1;
              while(i <= v){ /// monta o vetor
                  update(i,vet[i-1],v);
                  i++;
              }
          }
          else if(charInformado=='?'){
  
              printf("%d\n",get(abduzidoOuMostraValores-1));
          }
      }
      return 0;
  }

• 

  0

  crussi replied 8 years ago

  Este problema necessita de uma Bynari Indexed Tree. Eu te aconselho apenas a entender o que a BIT faz sem se preocupar em entender o seu código de imediato.

• 

  0

  DanielSantos replied 8 years ago

  Alguma dica? estou recebendo TLE abrass

  #include <iostream>
  #include <string.h>
  #include <stdio.h>
  
  using namespace std;
  
  int main()
  {
      int n;
      cin >> n;
      int v[n], soma = 0;
      memset(v, 0, sizeof(v));
      for(int i = 1; i <= n; i++)
      {
          int x;
          cin >> x;
          v[i] += x;
       }
      char a;
      int x;
      while(cin >> a >> x)
      {
          if(a == 'a')
          {
              v[x] = 0;
          }
          else if(a == '?')
          {
              for(int i = 1; i < x; i++)
              {
                  soma += v[i];
  
              }
              cout << soma << endl;
              soma = 0;
          }
      }
  
      return 0;
  }