fork download
copy 
  1. #include <cstdio>
  2.  
  3. const int N = 100001;
  4. const int LG = 31;
  5. int q;
  6.  
  7. int gcd(int a, int b)
  8. {
  9.     int t;
  10.     while (b)
  11.     {
  12.         a = a % b;
  13.         t = a;
  14.         a = b;
  15.         b = t;
  16.     }
  17.     return a;
  18. }
  19.  
  20. struct Node
  21. {
  22.     int f, g;
  23.     Node *l, *r;
  24.  
  25.     Node(int f_ = 0, int g_ = 0)
  26.     {
  27.         f = f_;
  28.         g = g_;
  29.         l = r = 0;
  30.     };
  31. };
  32.  
  33. Node pool[LG * N];
  34. int p = 0;
  35.  
  36. Node *new_node(int f, int g)
  37. {
  38.     pool[p].f = f;
  39.     pool[p].g = g;
  40.     return &pool[p++];
  41. }
  42.  
  43. Node *update(Node *t, int i, int v, int l = 1, int r = 1000000000)
  44. {
  45.     if(l == r) {
  46.         if(t == 0) return new_node(1, i);
  47.         else {
  48.             t->f += v;
  49.             if(t->f == 0) return 0;
  50.             return t;
  51.         }
  52.     }
  53.  
  54.     if(t == 0)
  55.         t = new_node(0, 0);
  56.  
  57.     int m = (l + r) / 2;
  58.     if(i > m) t->r = update(t->r, i, v, m + 1, r);
  59.     else t->l = update(t->l, i, v, l, m);
  60.  
  61.     t->g = gcd((t->l?t->l->g:0), (t->r?t->r->g:0));
  62.  
  63.     return t;
  64. }
  65.  
  66. int main(int argc, char *argv[])
  67. {
  68.     Node *t = 0;
  69.  
  70.     scanf("%d", &q);
  71.     for(int i = 0; i < q; i++)
  72.     {
  73.         char c[3];
  74.         int x;
  75.  
  76.         scanf("%1s %d", c, &x);
  77.         if(c[0] == '+') t = update(t, x, 1);
  78.         else t = update(t, x, -1);
  79.  
  80.         printf("%d\n", t->g == 0 ? 1 : t->g);
  81.     }
  82.     return 0;
  83. }
  84.  
Success #stdin #stdout 0.03s 51736KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/uyQVn2
timus_1846
language:
C++14 (gcc 8.3)
created:
10 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!