fork download
copy 
  1. /*TIMUS:
  2. Segment tree:
  3. Offline for compression
  4. NlogN
  5. */
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8. #define N 131072
  9. struct ques{
  10. 	int l,r;
  11. };
  12. ques q[2*N+2];
  13. int a[N], b[N], cnt[N];
  14.  
  15. int gcd(int a, int b){
  16. 	if(a>b) swap(a,b);
  17. 	if(a==0) return b;
  18. 	return gcd(a,b%a);
  19. }
  20.  
  21. void update(int idx, int val) {
  22. 	idx+=N; // indexed from 1 
  23. 	q[idx].l = val; 
  24. 	while(idx/2>=1){
  25. 		int lc = 2*(idx/2);
  26. 		int rc = lc+1;
  27. 		idx/=2;
  28. 		q[idx].l = gcd(q[lc].l,q[lc].r);
  29. 		q[idx].r = gcd(q[rc].l,q[rc].r);
  30. 	}
  31.  
  32. }
  33.  
  34. int query(){ return gcd(q[1].l,q[1].r); }
  35.  
  36. int main(){
  37.  
  38. 	int n;	
  39. 	cin>>n;
  40. 	for(int i = 0;i<n;i++){
  41. 		char c;
  42. 		cin>>c>>a[i];
  43. 		b[i] = a[i] = (c=='+')?a[i]:-a[i];
  44. 	}
  45.  
  46. 	sort(b,b+n);
  47. 	for(int i=0;i<n;i++){
  48. 		int pos = lower_bound(b,b+n,(a[i]>0?a[i]:-a[i]))-b;
  49.  
  50. 		if(a[i]>0)
  51. 			cnt[pos]++;
  52. 		else
  53. 			cnt[pos]--;
  54. 		if(a[i]>0 && cnt[pos] == 1) 
  55. 			update(pos,a[i]);
  56.  
  57. 		if(cnt[pos] == 0 && a[i]<0)
  58. 			update(pos,0);
  59. 		int res = query();
  60.  
  61. 		printf("%d\n",(res==0) ? 1:res);
  62. 	}
  63.  
  64. 	return 0;
  65. }
Success #stdin #stdout 0s 6732KB
comments (?)
stdin
copy 
4
+ 8
+ 8
- 8
- 8
stdout
copy 
8
8
8
1
https://ideone.com/uMRGOV
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!