fork(1) download
  1. #include <cstdio>
  2. #include <map>
  3.  
  4. #define maxN 100010
  5.  
  6. using namespace std;
  7.  
  8. int tree[maxN*4 + 1];
  9. map< int, int > pos, freq;
  10. char sign;
  11. int num, f, q, last;
  12.  
  13. inline int gcd( int a, int b ) {
  14. int r;
  15.  
  16. while( b != 0 ) {
  17. r = a % b;
  18. a = b;
  19. b = r;
  20. }
  21.  
  22. return a;
  23. }
  24.  
  25. inline void update( int idx, int l, int r, int p, int val ) {
  26. if( l == r ) {
  27. tree[idx] += val;
  28. return;
  29. } else {
  30. int mid = (l + r) / 2;
  31.  
  32. if( p <= mid )
  33. update(idx*2, l, mid, p, val);
  34. else
  35. update(idx*2+1, mid+1, r, p, val);
  36. }
  37.  
  38. tree[idx] = gcd(tree[idx*2], tree[idx*2 + 1]);
  39. }
  40.  
  41. int main( void ) {
  42.  
  43. // freq[i] : frquency of number (i), pos[i] : position of number (i) in the list
  44.  
  45. scanf("%i", &q);
  46.  
  47. last = 1;
  48. while( q-- ) {
  49. scanf(" %c%i", &sign, &num);
  50.  
  51. if( sign == '-' ) {
  52. f = --freq[num];
  53.  
  54. if( f == 0 ) {
  55. // should remove it
  56. update(1, 0, maxN-1, pos[num], -num);
  57. pos[num] = 0;
  58. }
  59.  
  60. } else {
  61. f = freq[num]++;
  62.  
  63. if( f == 0 ) {
  64. // it didn't exists in the list must add it
  65. update(1, 0, maxN-1, last, num);
  66. pos[num] = last;
  67. }
  68. }
  69.  
  70. last++;
  71. printf("%i\n", tree[1] == 0 ? 1 : tree[1]);
  72. }
  73.  
  74. return 0;
  75. }
Success #stdin #stdout 0s 4908KB
stdin
Standard input is empty
stdout
Standard output is empty