fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define rep(i,begin,end) for(int i=begin;i<=end;i++)
  4. #define repi(i,end,begin) for(int i=end;i>=begin;i--)
  5. #define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  6.  
  7. using namespace std;
  8.  
  9. struct Tree{
  10. 	multiset<int> ms;
  11. 	multiset<int>::iterator med_it;
  12. 	int med_idx;
  13. };
  14.  
  15. int Ceil(int a, int b){
  16. 	return (a+1)/b;
  17. }
  18.  
  19. void initializeTree(Tree (&tree), int el){
  20. 	(tree.ms).insert(el);
  21. 	(tree.med_it) = (tree.ms).begin();
  22. 	(tree.med_idx) = 1;
  23. }
  24.  
  25. void TreeInsert(Tree (&tree), int el){
  26. 	(tree.ms).insert(el);
  27.  
  28. 	if(el < *(tree.med_it)) (tree.med_idx)++;
  29.  
  30. 	int idx = Ceil((tree.ms).size(),2);
  31.  
  32. 	if(tree.med_idx < idx) (tree.med_it)++;
  33. 	else if(tree.med_idx > idx) (tree.med_it)--;
  34.  
  35. 	tree.med_idx = idx;
  36. }
  37.  
  38. void TreeDelete(Tree (&tree), int el){
  39. 	multiset<int>::iterator aux;
  40.  
  41. 	int idx = Ceil((int)(tree.ms).size() - 1,2);
  42.  
  43. 	if(el == *(tree.med_it)){
  44. 		aux = (tree.med_it);
  45.  
  46. 		if((tree.med_idx) == idx) aux++;
  47. 		else aux--;
  48.  
  49. 		(tree.ms).erase((tree.med_it));
  50. 		(tree.med_it) = aux;
  51. 	}
  52. 	else{
  53. 		aux = (tree.ms).find(el);
  54. 		(tree.ms).erase(aux);
  55.  
  56. 		if(el < *(tree.med_it)) (tree.med_idx)--;
  57.  
  58. 		if((tree.med_idx) < idx) (tree.med_it)++;
  59. 		else if((tree.med_idx) > idx) (tree.med_it)--;
  60. 	}
  61.  
  62. 	(tree.med_idx) = idx; 
  63. }
  64.  
  65. int TreeMerge(Tree (&tree1), Tree (&tree2)){
  66. 	multiset<int>::iterator it;
  67.  
  68. 	if((tree1.ms).size() >= (tree2.ms).size()){
  69. 		for(it = (tree2.ms).begin(); it != (tree2.ms).end(); it++) TreeInsert(tree1, *it);
  70. 		return 1;
  71. 	}
  72. 	else{
  73. 		for(it = (tree1.ms).begin(); it != (tree1.ms).end(); it++) TreeInsert(tree2, *it);
  74. 		return 2;
  75. 	}
  76. }
  77.  
  78. int main(){
  79. fio
  80.  
  81. Tree tree1, tree2;
  82.  
  83. initializeTree(tree1,9);
  84. initializeTree(tree2,4);
  85.  
  86. list<Tree> L;
  87.  
  88. L.push_back(tree1);
  89. L.push_back(tree2);
  90.  
  91. list<Tree>::iterator L_cur = L.begin(), L_next = L.begin();
  92. L_next++;
  93.  
  94. multiset<int>::iterator it;
  95.  
  96. cout << "Items of first tree before merge: ";
  97.  
  98. for(it = ((*L_cur).ms).begin(); it != ((*L_cur).ms).end(); it++) cout << *it << " ";
  99. cout << '\n';
  100.  
  101. cout << "Median index for first tree before merge: ";
  102. cout << (*L_cur).med_idx << '\n';
  103.  
  104. cout << "Median value for first tree before merge: ";
  105. cout << *((*L_cur).med_it) << '\n';
  106.  
  107. cout << "Items of second list before merge: ";
  108.  
  109. multiset<int>::iterator it2;
  110.  
  111. for(it = ((*L_next).ms).begin(); it != ((*L_next).ms).end(); it++) cout << *it << " ";
  112. cout << '\n';
  113.  
  114. cout << "Median index for second tree before merge: ";
  115. cout << (*L_next).med_idx << '\n';
  116.  
  117. cout << "Median value for second tree before merge: ";
  118. cout << *((*L_next).med_it) << '\n';
  119.  
  120. int merge = TreeMerge(*L_cur,*L_next);
  121.  
  122. cout << "Items of first tree after merge: ";
  123.  
  124. for(it = ((*L_cur).ms).begin(); it != ((*L_cur).ms).end(); it++) cout << *it << " ";
  125. cout << '\n';
  126.  
  127. cout << "Median index for first tree after merge: ";
  128. cout << (*L_cur).med_idx << '\n';
  129.  
  130. cout << "Median value for first tree after merge: ";
  131. cout << *((*L_cur).med_it) << '\n';
  132.  
  133. cout << "Items of second list after merge: ";
  134.  
  135. for(it = ((*L_next).ms).begin(); it != ((*L_next).ms).end(); it++) cout << *it << " ";
  136. cout << '\n';
  137.  
  138. cout << "Median index for second tree after merge: ";
  139. cout << (*L_next).med_idx << '\n';
  140.  
  141. cout << "Median value for second tree after merge: ";
  142. cout << *((*L_next).med_it) << '\n';
  143. return 0;
  144. }
Success #stdin #stdout 0s 4460KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Items of first tree before merge: 9 
Median index for first tree before merge: 1
Median value for first tree before merge: 9
Items of second list before merge: 4 
Median index for second tree before merge: 1
Median value for second tree before merge: 4
Items of first tree after merge: 4 9 
Median index for first tree after merge: 1
Median value for first tree after merge: 9
Items of second list after merge: 4 
Median index for second tree after merge: 1
Median value for second tree after merge: 4
https://ideone.com/VgwL4d
language:
C++14 (gcc 8.3)
created:
5 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!