fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Skip_lists;
  5. struct Column;
  6. struct Cell;
  7.  
  8.  
  9.  
  10. struct Skip_lists {
  11. 	static const int MAX_LEVEL = 20;
  12. 	Column *head, *tail;
  13.  
  14. 	Skip_lists();
  15. 	bool empty();
  16. 	Column *lower_bound(int);
  17. 	Column *upper_bound(int);
  18. 	void insert(int);
  19. 	void erase(int);
  20. };
  21.  
  22. struct Column {
  23. 	int value;
  24. 	vector<Cell> cells;
  25. };
  26.  
  27. struct Cell {
  28. 	Column *previous_column, *next_column;
  29. };
  30.  
  31.  
  32.  
  33. Skip_lists::Skip_lists() {
  34. 	head = new Column;
  35. 	tail = new Column;
  36. 	head->value = 0;
  37. 	tail->value = 0;
  38. 	for(int i = 0; i < MAX_LEVEL; i++) {
  39. 		head->cells.push_back((Cell){NULL, tail});
  40. 		tail->cells.push_back((Cell){head, NULL});
  41. 	}
  42. }
  43.  
  44. bool Skip_lists::empty() {
  45. 	return head->cells[0].next_column == tail;
  46. }
  47.  
  48. Column *Skip_lists::lower_bound(int value) {
  49. 	Column *iter = head;
  50. 	for(int level = MAX_LEVEL - 1; level >= 0; level--) {
  51. 		while(iter->cells[level].next_column != tail && iter->cells[level].next_column->value < value) {
  52. 			iter = iter->cells[level].next_column;
  53. 		}
  54. 	}
  55. 	return iter->cells[0].next_column;
  56. }
  57.  
  58. Column *Skip_lists::upper_bound(int value) {
  59. 	Column *iter = head;
  60. 	for(int level = MAX_LEVEL - 1; level >= 0; level--) {
  61. 		while(iter->cells[level].next_column != tail && iter->cells[level].next_column->value <= value) {
  62. 			iter = iter->cells[level].next_column;
  63. 		}
  64. 	}
  65. 	return iter->cells[0].next_column;
  66. }
  67.  
  68. void Skip_lists::insert(int value) {
  69. 	Column *temp = lower_bound(value);
  70. 	if(temp != tail && temp->value == value) {
  71. 		return;
  72. 	}
  73. 	Column *inserted_column = new Column;
  74. 	inserted_column->value = value;
  75. 	inserted_column->cells.push_back((Cell){NULL, NULL});
  76. 	while(inserted_column->cells.size() < MAX_LEVEL && rand() % 2 == 0) {
  77. 		inserted_column->cells.push_back((Cell){NULL, NULL});
  78. 	}
  79. 	Column *iter = head;
  80. 	for(int level = MAX_LEVEL - 1; level >= 0; level--) {
  81. 		while(iter->cells[level].next_column != tail && iter->cells[level].next_column->value < value) {
  82. 			iter = iter->cells[level].next_column;
  83. 		}
  84. 		if(level < inserted_column->cells.size()) {
  85. 			Column *next_iter = iter->cells[level].next_column;
  86. 			iter->cells[level].next_column = inserted_column;
  87. 			next_iter->cells[level].previous_column = inserted_column;
  88. 			inserted_column->cells[level].previous_column = iter;
  89. 			inserted_column->cells[level].next_column = next_iter;
  90. 		}
  91. 	}
  92. }
  93.  
  94. void Skip_lists::erase(int value) {
  95. 	Column *erased_column = lower_bound(value);
  96. 	if(erased_column == tail || erased_column->value != value) {
  97. 		return;
  98. 	}
  99. 	Column *iter = head;
  100. 	for(int level = MAX_LEVEL - 1; level >= 0; level--) {
  101. 		while(iter->cells[level].next_column != tail && iter->cells[level].next_column->value <= value) {
  102. 			iter = iter->cells[level].next_column;
  103. 		}
  104. 		if(iter == erased_column) {
  105. 			Column *previous_iter = iter->cells[level].previous_column, *next_iter = iter->cells[level].next_column;
  106. 			previous_iter->cells[level].next_column = next_iter;
  107. 			next_iter->cells[level].previous_column = previous_iter;
  108. 		}
  109. 	}
  110. 	delete erased_column;
  111. }
  112.  
  113.  
  114.  
  115. Skip_lists sl;
  116.  
  117. int main() {
  118. 	//ifstream cin("cppset.inp");
  119. 	//ofstream cout("cppset.out");
  120. 	ios_base::sync_with_stdio(false);
  121. 	cin.tie(NULL);
  122. 	int query_type, value;
  123. 	while(cin >> query_type) {
  124. 		if(query_type == 0) {
  125. 			break;
  126. 		}
  127. 		else if(query_type == 1) {
  128. 			cin >> value;
  129. 			sl.insert(value);
  130. 		}
  131. 		else if(query_type == 2) {
  132. 			cin >> value;
  133. 			sl.erase(value);
  134. 		}
  135. 		else if(query_type == 3) {
  136. 			if(sl.empty()) {
  137. 				cout << "empty\n";
  138. 			}
  139. 			else {
  140. 				cout << sl.head->cells[0].next_column->value << "\n";
  141. 			}
  142. 		}
  143. 		else if(query_type == 4) {
  144. 			if(sl.empty()) {
  145. 				cout << "empty\n";
  146. 			}
  147. 			else {
  148. 				cout << sl.tail->cells[0].previous_column->value << "\n";
  149. 			}
  150. 		}
  151. 		else if(query_type == 5) {
  152. 			cin >> value;
  153. 			if(sl.empty()) {
  154. 				cout << "empty\n";
  155. 			}
  156. 			else {
  157. 				Column *found_column = sl.upper_bound(value);
  158. 				if(found_column == sl.tail) {
  159. 					cout << "no\n";
  160. 				}
  161. 				else {
  162. 					cout << found_column->value << "\n";
  163. 				}
  164. 			}
  165. 		}
  166. 		else if(query_type == 6) {
  167. 			cin >> value;
  168. 			if(sl.empty()) {
  169. 				cout << "empty\n";
  170. 			}
  171. 			else {
  172. 				Column *found_column = sl.lower_bound(value);
  173. 				if(found_column == sl.tail) {
  174. 					cout << "no\n";
  175. 				}
  176. 				else {
  177. 					cout << found_column->value << "\n";
  178. 				}
  179. 			}
  180. 		}
  181. 		else if(query_type == 7) {
  182. 			cin >> value;
  183. 			if(sl.empty()) {
  184. 				cout << "empty\n";
  185. 			}
  186. 			else {
  187. 				Column *found_column = sl.lower_bound(value)->cells[0].previous_column;
  188. 				if(found_column == sl.head) {
  189. 					cout << "no\n";
  190. 				}
  191. 				else {
  192. 					cout << found_column->value << "\n";
  193. 				}
  194. 			}
  195. 		}
  196. 		else {
  197. 			cin >> value;
  198. 			if(sl.empty()) {
  199. 				cout << "empty\n";
  200. 			}
  201. 			else {
  202. 				Column *found_column = sl.upper_bound(value)->cells[0].previous_column;
  203. 				if(found_column == sl.head) {
  204. 					cout << "no\n";
  205. 				}
  206. 				else {
  207. 					cout << found_column->value << "\n";
  208. 				}
  209. 			}
  210. 		}
  211. 	}
  212. 	return 0;
  213. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/53t3Eh
language:
C++ (gcc 8.3)
created:
6 years 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!