Advertisement
Gustavo_Inzunza

GCD (INCOMPLETO)

Jul 18th, 2013
54
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.68 KB | None | 0 0
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <vector>
  4. #include <algorithm>
  5. #define LEFT(n) (2(n))
  6. #define RIGHT (n) (2(n)+1)
  7. #define NEUT 2147483647
  8.  
  9. using namespace std;
  10. vector<int> numeros;
  11. int arbol[2000000];
  12. int oper(int a,int b)
  13. {
  14.     if(!a)
  15.         return b;
  16.     return oper(b%a,a);
  17. }
  18. void constructor(int nodo,int izq,int der)
  19. {
  20.     if(izq==der)
  21.     {
  22.         arbol[nodo]=numeros[izq];
  23.         return;
  24.     }
  25.     int mitad=(izq+der)/2;
  26.     constructor(2*nodo,izq,mitad);
  27.     constructor(2*nodo+1,mitad+1,der);
  28.     arbol[nodo]=oper(arbol[2*nodo],arbol[2*nodo+1]);
  29. }
  30. int consulta(int nodo,int izq,int der,int start,int end)
  31. {
  32.     if(end<izq || start>der)
  33.         return NEUT;
  34.     if(start>=izq and end<=der)
  35.         return arbol[nodo];
  36.     int respuesta_izq=consulta(2*nodo,izq,(izq+der)/2,start,end);
  37.     int respuesta_der=consulta(2*nodo+1,(izq+der)/2+1,der,start,end);
  38.     return oper(respuesta_izq,respuesta_der);
  39. }
  40. void update(int nodo,int izq,int der,int pos,int valor)
  41. {
  42.     if(pos<izq || pos>der)
  43.         return;
  44.     if(izq==der)
  45.     {
  46.         arbol[nodo]=numeros[izq]=valor;
  47.         return;
  48.     }
  49.     int mitad=(izq+der)/2;
  50.     if(pos<mitad)
  51.         update(2*nodo,izq,mitad,pos,valor);
  52.     else
  53.         update(2*nodo+1,mitad+1,der,pos,valor);
  54.     arbol[nodo]=oper(arbol[2*nodo],arbol[2*nodo+1]);
  55. }
  56. int main()
  57. {
  58.     int N,aux;
  59.     char aux2;
  60.     scanf("%d",&N);
  61.     for(int i=0;i<N;i++)
  62.     {
  63.         cin>>aux2>>aux;
  64.         if(aux2=='+')
  65.             numeros.push_back(aux);
  66.         else
  67.         {
  68.             for(int j=0;j<numeros.size();j++)
  69.                 if(numeros[j]==aux)
  70.                 {
  71.                     numeros.erase(numeros.begin()+j);
  72.                     break;
  73.                 }
  74.         }
  75.         if(numeros.empty())
  76.         {
  77.             printf("1\n");
  78.             continue;
  79.         }
  80.         constructor(0,0,numeros.size()-1);
  81.         printf("%d\n",consulta(0,0,numeros.size()-1,0,numeros.size()-1));
  82.     }
  83.    
  84. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement