fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define fastIo ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  4. #define f(i,n) for(int i=1;i<=n;i++)
  5. #define f3(i,l,r) for(int i=l;i<=r;i++)
  6. #define pb push_back
  7. #define int long long
  8. #define ff first
  9. #define ALL(v) v.begin(),v.end()
  10. #define pii pair<int,int>
  11. #define ss second
  12. #define tree preihjpoueheaopuhjew
  13. const int N=1e5+100;
  14. int n;
  15. pii query[N];
  16. int limit;
  17. int max(int a,int b) {
  18. 	return a>b?a:b;
  19. }
  20. vector<int>comp;
  21. struct tree {
  22. 	int cnt,g;
  23. 	tree(int _g=0,int _cnt=0) {
  24. 		g=_g;
  25. 		cnt=_cnt;
  26. 	}
  27. 	void merge(tree left,tree right){
  28. 		g=__gcd(left.g,right.g);
  29. 	}
  30. };
  31. tree stGcd[4*N];
  32. int __gcd(int a,int b) {
  33. 	return b==0?a:__gcd(b,a%b);
  34. }
  35. int compress() {
  36. 	for (int i = 1; i <= n; i++) {
  37. 		comp.pb(query[i].ss);
  38. 	}
  39. 	sort(ALL(comp));
  40. 	comp.resize(unique(ALL(comp)) - comp.begin());
  41. 	for (int i = 1; i <= n; i++) {
  42. 		query[i].ss = lower_bound(ALL(comp), query[i].ss) - comp.begin() + 1;
  43. 	}
  44. 	return comp.size();
  45. }
  46. void updateGcdTree(int ix,int v,int i=1,int l=1,int r=limit) {
  47. 	if(!(l<=ix&&ix<=r))return;
  48. 	if(l==r&&l==ix){
  49. 		stGcd[i].cnt+=v;
  50. 		if(stGcd[i].cnt>=1)stGcd[i].g=comp[l-1];
  51. 		else stGcd[i].g=0;
  52. 		return;
  53. 	}
  54. 	int m=(l+r)>>1,cl=2*i,cr=2*i+1;
  55. 	updateGcdTree(ix,v,cl,l,m);
  56. 	updateGcdTree(ix,v,cr,m+1,r);
  57. 	stGcd[i].merge(stGcd[cl],stGcd[cr]);
  58. }
  59. tree queriesGcdTree(int u,int v,int i=1,int l=1,int r=limit) {
  60. 	if(l>v||r<u)return tree();
  61. 	if(u<=l&&v>=r)return stGcd[i];
  62. 	int m=(l+r)>>1,cl=2*i,cr=2*i+1;
  63. 	tree ans;
  64. 	ans.merge(queriesGcdTree(u,v,cl,l,m),queriesGcdTree(u,v,cr,m+1,r));
  65. 	return ans;
  66. }
  67. signed main() {
  68. 	fastIo;
  69. 	cin>>n;
  70. 	int cnt=0;
  71. 	f(i,n)cin>>query[i].ff>>query[i].ss;
  72. 	limit=compress();
  73. 	f(i,n) {
  74. 		int x=query[i].ss;
  75. 		//	cout<<"E:"<<x<<"\n";
  76. 		if(query[i].ff==1) {
  77. 			updateGcdTree(x,1);
  78. 		} else {
  79. 			updateGcdTree(x,-1);
  80. 		}
  81. 		auto ans=queriesGcdTree(1,limit);
  82. 		cout<<max(1LL,ans.g)<<"\n";
  83. 	}
  84.  
  85. }
Success #stdin #stdout 0.01s 11328KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/XFpCmC
language:
C++14 (gcc 8.3)
created:
120 days 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!