fork download
copy 
  1. /*
  2. Timus GCD2010
  3. BBST:  indexing like segment tree
  4. offline for compression/keeping count of elements.
  5. */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. #define N 100010
  11. struct node{
  12. 	int l,r,v;
  13. }; //need not use v but the main loop gets a bit ugly;
  14. node q[N];
  15. int a[N], b[N], cnt[N];
  16.  
  17. int gcd(int a, int b){
  18. 	if(a>b) swap(a,b);
  19. 	while(a>0){
  20. 		b%=a;
  21. 		swap(b,a);
  22. 	}
  23. 	return b;
  24. }
  25.  
  26.  
  27. void update(int idx, int val){
  28. 	q[idx].v = val; 
  29. 	for(;idx/2>0;idx/=2){		
  30. 		int lc = 2*(idx/2);
  31. 		int rc = lc+1;
  32. 		q[idx/2].l = gcd(q[lc].r,gcd(q[lc].v,q[lc].l));
  33. 		q[idx/2].r = gcd(q[rc].r,gcd(q[rc].v,q[rc].l));
  34. 		/*cout<<"gcd of "<<q[lc].l<<" "<<q[lc].r<<" "<<q[lc].v<<" is "<<q[idx].l<<" "<<lc<<" parent "<<idx/2<<endl;
  35. 		cout<<"gcd of "<<q[rc].l<<" "<<q[rc].r<<" "<<q[rc].v<<" is "<<q[idx].r<<" "<<rc<<" parent "<<idx/2<<endl;*/
  36.  
  37. 	}
  38. }
  39.  
  40. int query(){ return gcd(q[1].r,gcd(q[1].v,q[1].l)); }
  41.  
  42.  
  43. int main(){
  44. #ifndef ONLINE_JUDGE
  45. 	freopen("input.txt","r",stdin);
  46. #endif
  47.  
  48. 	int n;
  49. 	cin>>n;
  50. 	for(int i=0;i<n;i++){
  51. 		char c;
  52. 		cin>>c>>a[i];
  53. 		b[i] = a[i] = (c=='+')?a[i]:-a[i];
  54. 	}
  55. 	sort(b,b+n);
  56.  
  57. 	for(int i=0;i<n;i++){
  58. 		int pos = lower_bound(b,b+n,(a[i]<0?-a[i]:a[i]))-b+1;
  59. 		if(a[i]>0)
  60. 			cnt[pos]++;
  61. 		else
  62. 			cnt[pos]--;
  63.  
  64. 		if(a[i]>0 && cnt[pos] == 1)
  65. 			update(pos,a[i]); //pos is just an empty space. [can be any]
  66. 		if(a[i]<0 && cnt[pos] == 0)
  67. 			update(pos,0);
  68. 		int res = query();
  69. 		printf("%d\n",(res == 0)?1:res);
  70.  
  71. 	}
  72.  
  73. 	return 0;
  74. }
Success #stdin #stdout 0s 5448KB
comments (?)
stdin
copy 
4
+ 8
+ 8
- 8
- 8
stdout
copy 
8
8
8
1
https://ideone.com/wqH4Tz
language:
C++ (gcc 8.3)
created:
8 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!