fork(1) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/wwin7S
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!