fork download 
  1. # include <cstdio>
  2. using namespace std;
  3.  
  4. inline int gcd(int a, int b){ int t; while (b){ a = a%b; t = a; a = b; b = t; }return a; }
  5.  
  6. struct node
  7. {
  8. 	int l, r;
  9. 	int val;
  10. 	int fr;
  11. }; 
  12. node nodes[31*100000];
  13. int lastn = 2;
  14. void update(int& cur, int l, int r, int x, int y)
  15. {
  16. 	if (cur == 0)
  17. 		cur = lastn++;
  18.  
  19. 	if (l == r)
  20. 	{
  21. 		nodes[cur].fr += y;
  22. 		if (nodes[cur].fr == 0)
  23. 		{
  24. 			nodes[cur].val = 0;
  25. 		}
  26. 		else
  27. 		{
  28. 			nodes[cur].val = x;
  29. 		}
  30. 	}
  31. 	else
  32. 	{
  33. 		int m = (l + r) >> 1;
  34. 		if (x <= m)
  35. 		{
  36. 			update(nodes[cur].l, l, m, x, y);
  37. 		}
  38. 		else
  39. 		{
  40. 			update(nodes[cur].r, m + 1, r, x, y);
  41. 		}
  42. 		nodes[cur].val = gcd(nodes[nodes[cur].l].val, nodes[nodes[cur].r].val);
  43. 	}
  44. }
  45.  
  46. int main()
  47. {
  48. 	int n;
  49. 	scanf("%d", &n);
  50. 	int res = 0;
  51. 	int root = 1;
  52. 	while (n--)
  53. 	{
  54. 		char c;
  55. 		int x;
  56. 		scanf("\n%c %d", &c, &x);
  57. 		if (c == '+')
  58. 		{
  59. 			update(root, 1, 1000000000, x, 1);
  60. 		}
  61. 		else
  62. 		{
  63. 			update(root, 1, 1000000000, x, -1);
  64. 		}
  65. 		res = nodes[1].val;
  66. 		if (res == 0)
  67. 			res = 1;
  68. 		printf("%d\n", res);
  69. 	}
  70.  
  71. 	return 0;
  72. }
Success #stdin #stdout 0s 51784KB
comments (?)
stdin 
5
+ 8
+ 6
+ 8
- 8
- 8
stdout 
8
2
2
2
6
https://ideone.com/pcsvEL
5
+ 8
+ 6
+ 8
- 8
- 8
language:
C++ (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!