fork(1) download
copy 
  1. #include<iostream>
  2. using namespace std;
  3. #define ll long long
  4.  
  5. ll seed = 89698687;
  6.  
  7. int my_rand() {
  8. 	seed = seed * 1234567 + 3256236;
  9. 	return (unsigned int)(seed >> 16) & 0x7fffffff;
  10. }
  11.  
  12. struct Node {
  13. 	ll data, priority;
  14. 	int size, cnt;
  15. 	Node *left, *right;
  16. };
  17.  
  18. Node pool[1000005];
  19. int pool_size = 0;
  20.  
  21. Node *create(ll x) {
  22. 	Node *res = pool + pool_size++;
  23. 	res->data = x, res->size = res->cnt = 1, res->priority = my_rand() % 100, res->left = res->right = 0;
  24. 	return res;
  25. }
  26.  
  27. int getSize(Node *node) {
  28. 	return node ? node->size : 0;
  29. }
  30.  
  31. void upd_size(Node *node) {
  32. 	if(node) node->size = node->cnt + getSize(node->left) + getSize(node->right);
  33. }
  34.  
  35. Node *leftRotate(Node *node) {
  36. 	Node *a = node->right, *b = a->left;
  37. 	a->left = node;
  38. 	node->right = b;
  39. 	a->size = node->size;
  40. 	upd_size(node);
  41. 	return a;
  42. }
  43.  
  44. Node *rightRotate(Node *node) {
  45. 	Node *a = node->left, *b = a->right;
  46. 	a->right = node;
  47. 	node->left = b;
  48. 	a->size = node->size;
  49. 	upd_size(node);
  50. 	return a;
  51. }
  52.  
  53. Node *tmp, *root = 0;
  54.  
  55. Node *add(Node *node, ll x) {
  56. 	if(!node) return create(x);
  57. 	if(x < node->data) {
  58. 		node->left = add(node->left, x);
  59. 		if(node->left->priority > node->priority) node = rightRotate(node);
  60. 	}
  61. 	else if(x > node->data) {
  62. 		node->right = add(node->right, x);
  63. 		if(node->right->priority > node->priority) node = leftRotate(node);
  64. 	}
  65. 	else node->cnt++;
  66. 	upd_size(node);
  67. 	return node;
  68. }
  69.  
  70. Node *getNode(ll x) {
  71. 	Node *cur = root;
  72. 	while(cur) {
  73. 		if(cur->data == x) return cur;
  74. 		if(x < cur->data) cur = cur->left;
  75. 		else cur = cur->right;
  76. 	}
  77. 	return 0;
  78. }
  79.  
  80. Node *select(Node *node, int k) {
  81. 	if(!node) return 0;
  82. 	int t = getSize(node->left);
  83. 	if(k < t) return node->left ? select(node->left, k) : node;
  84. 	else {
  85. 		if(k - t < node->cnt) return node;
  86. 		return node->right ? select(node->right, k - t - node->cnt) : node;
  87. 	}
  88. 	return node;
  89. }
  90.  
  91. void printTree(Node *node) {
  92. 	if(!node) return;
  93. 	printTree(node->left);
  94. 	for(int i = 0; i < node->cnt; ++i) cout << node->data << ' ';
  95. 	printTree(node->right);
  96. }
  97.  
  98. int main() {
  99. 	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  100. //	freopen("input.txt", "r", stdin);
  101. 	int n, x; cin >> n;
  102. 	for(int i = 0; i < n; ++i) {
  103. 		cin >> x;
  104. 		root = add(root, x);
  105. 		tmp = select(root, i / 2);
  106. 		cout << tmp->data << ' ';
  107. 	}
  108. 	cout << '\n';
  109.  
  110. 	return 0;
  111. }
  112.  
  113.  
Success #stdin #stdout 0s 4276KB
comments (?)
stdin
copy 
9
7 4 2 1 6 8 5 8 7
stdout
copy 
7 4 4 2 4 4 5 5 6
https://ideone.com/jwiM89
language:
C++ (gcc 8.3)
created:
4 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!