fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define endl '\n'
  4. #define left jhghajkhja
  5. #define right oauighgajk
  6. #define prev aioghajga
  7. #define next ioyhjhfajasj
  8. #define y0 iuadoghasdgj
  9. #define y1 taklahgjkla
  10. #define remainder pogjuakllhga
  11. #define pow pajklgaklha
  12. #define pow10 iopuioadjlgkah
  13. #define div aljghajkghak
  14. #define distance gkuftgjasgfjh
  15. #define uppercase ifyhasjkhakjfas
  16. #define count sajhfkajfa
  17.  
  18. //#define floor hjakjhaja
  19. //#define time ashjlahjka
  20. //#define double_t double
  21. //#define tm kahjflahaajk
  22.  
  23. using namespace std;
  24.  
  25. const int N = 1<<17;
  26. const int TREE_SIZE = N<<2;
  27.  
  28. int q;
  29. char type[N];
  30. int number[N];
  31. int p[N],sz,all;
  32. map < int, int > code;
  33. int restore[N];
  34. map < int, int > m;
  35. int tree[TREE_SIZE];
  36. int arr[TREE_SIZE];
  37.  
  38. int gcd(int a, int b) {
  39. 	if(a==0 && b==0) return 0;
  40. 	int r;
  41. 	while(b) r=a%b,a=b,b=r;
  42. 	return a;
  43. }
  44.  
  45. void update_tree(int a, int b, int pos, int node, int value) {
  46. 	if(a>b || a>pos || b<pos) return;
  47. 	if(a==b) {
  48. 		tree[node]+=value;
  49. 		return;
  50. 	}
  51. 	update_tree(a,(a+b)>>1,pos,node<<1,value);
  52. 	update_tree(((a+b)>>1)+1,b,pos,(node<<1)|1,value);
  53. 	tree[node]=gcd(tree[node<<1],tree[(node<<1)|1]);
  54. }
  55.  
  56. int main() {
  57. 	ios_base::sync_with_stdio(false);
  58. 	cin.tie(NULL);
  59. 	//freopen("test.txt","r",stdin);
  60. 	//freopen("IN.c_str()","r",stdin);
  61. 	//freopen("OUT.c_str()","w",stdin);
  62. 	int i;
  63.  
  64. 	cin>>q;
  65. 	for(i=1;i<=q;i++) {
  66. 		cin>>type[i]>>number[i];
  67. 		p[++sz]=number[i];
  68. 	}
  69. 	sort(p+1,p+1+sz);
  70. 	code[p[1]]=1;
  71. 	restore[1]=code[p[1]];
  72. 	all=1;
  73. 	for(i=2;i<=sz;i++) {
  74. 		if(p[i]!=p[i-1]) {
  75. 			++all;
  76. 			code[p[i]]=all;
  77. 			restore[all]=p[i];
  78. 		}
  79. 	}
  80. 	for(i=1;i<=q;i++) {
  81. 		if(type[i]=='+') {
  82. 			++m[number[i]];
  83. 			if(m[number[i]]==1) update_tree(1,all,code[number[i]],1,number[i]);
  84. 		}
  85. 		else {
  86. 			--m[number[i]];
  87. 			if(m[number[i]]==0) update_tree(1,all,code[number[i]],1,-number[i]);
  88. 		}
  89. 		printf("%d\n", ((tree[1]==0) ? 1 : tree[1]));
  90. 	}
  91.  
  92. 	//fprintf(stderr, "Time: %d ms\n", (int)(clock()*1000.0/CLOCKS_PER_SEC));
  93.  
  94. 	return 0;
  95. }
  96.  
Success #stdin #stdout 0s 9216KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/uJ8ndT
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!