fork(3) download
copy 
  1. #include<iostream>
  2.  
  3. using namespace std;
  4.  
  5.  
  6. class Maxsegtree
  7. {
  8. 	int* P;
  9. 	int* Q;
  10. 	public:
  11. 		Maxsegtree(int N)
  12. 		{
  13. 			P=new int[N];
  14. 			Q=new int[2*N];
  15. 		}
  16.  
  17.  
  18. 		~Maxsegtree()
  19. 		{
  20. 			delete []P;
  21. 			delete []Q;
  22. 		}
  23.  
  24. 		int getP(int i) { return P[i];}
  25.  
  26. 		void setP(int i,int x){ P[i]=x; }
  27.  
  28. 		void build_tree(int node,int l,int r)
  29. 		{
  30. 			if(l==r)
  31. 				Q[node]=l;
  32. 			else
  33. 			{
  34. 				build_tree(node*2,l,(l+r)/2);
  35. 				build_tree(node*2+1,(l+r)/2+1,r);
  36.  
  37. 				if(P[Q[2*node]] > P[Q[2*node+1]])
  38. 					Q[node]=Q[2*node];
  39. 				else
  40. 					Q[node]=Q[2*node+1];
  41. 			}
  42. 		}
  43.  
  44. };
  45.  
  46.  
  47. class Minsegtree
  48. {
  49. 	int *A;
  50. 	int *B;
  51. 	public:
  52. 		Minsegtree(int N)
  53. 		{
  54. 			A=new int[N];
  55. 			B=new int[2*N];
  56. 		}
  57.  
  58. 		~Minsegtree()
  59. 		{
  60. 			delete []A;
  61. 			delete []B;
  62. 		}
  63.  
  64. 		int getA(int i){return A[i];}
  65.  
  66. 		void setA(int i,int x){A[i]=x;}
  67.  
  68. 		void build_mintree(int node,int l,int r)
  69. 		{
  70. 			if(l==r)
  71. 				B[node]=l;
  72. 			else
  73. 			{
  74. 				build_mintree(node*2,l,(l+r)/2);
  75. 				build_mintree(node*2+1,(l+r)/2+1,r);
  76.  
  77. 				if(A[B[2*node]] <= A[B[2*node+1]])
  78. 					B[node]=B[2*node];
  79. 				else
  80. 					B[node]=B[2*node+1];
  81. 			}
  82. 		}
  83. };
  84.  
  85.  
  86. int main()
  87. {
  88. 	int n;
  89. 	int x;
  90. 	cin>>n;
  91. 	Minsegtree mint(n);
  92. 	Maxsegtree maxt(n);
  93.  
  94. 	for(int i=0;i<n;i++)
  95. 	{
  96. 		cin>>x;
  97. 		mint.setA(i,x);
  98. 		maxt.setP(i,x);
  99. 	}
  100.  
  101. 	cout<<"Before function is called"<<endl;
  102. 	for(int i=0;i<n;i++)
  103. 		cout<<maxt.getP(i)<<" ";
  104. 	cout<<endl;
  105.  
  106. 	mint.build_mintree(1,0,n-1);
  107.  
  108.  
  109. 	cout<<"After function is called"<<endl;
  110. 	for(int i=0;i<n;i++)
  111. 		cout<<maxt.getP(i)<<" ";
  112. 	cout<<endl;
  113.  
  114. 	return 0;
  115. }
Success #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
18
3 4 2 1 5 7 9 7 10 5 12 3 1 1 2 1 3 2
stdout
copy 
Before function is called
3 4 2 1 5 7 9 7 10 5 12 3 1 1 2 1 3 2 
After function is called
3 4 2 1 5 7 9 7 10 5 9 10 1 1 2 1 3 2
https://ideone.com/9zDgU0
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!