fork download
  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
stdin
Standard input is empty
stdout
Standard output is empty