fork(1) download
  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
stdin
Standard input is empty
stdout
Standard output is empty