fork download
  1.  
  2. const int INF=2e9;
  3.  
  4. struct skip_list
  5. {
  6. struct node
  7. {
  8. int num;
  9. vector<node*> nxt;
  10. vector<node*> prv;
  11. vector<int> nxt_len;
  12. vector<int> prv_len;
  13. node(int x):num(x){}
  14. } *begin,*end;
  15.  
  16. int size;
  17.  
  18. skip_list()
  19. {
  20. size=0;
  21. begin=new node(-INF);
  22. end =new node(+INF);
  23. begin->nxt={ end};
  24. end ->prv={begin};
  25. begin->nxt_len=end->prv_len={1};
  26. }
  27.  
  28. node *find_by_order(int x)
  29. {
  30. node *cur=begin;
  31. int cl=begin->nxt.size();
  32. int cx=-1;
  33. while(cl>=0)
  34. {
  35. while(cl<cur->nxt.size() && cx+cur->nxt_len[cl]<x)
  36. {
  37. cx+=cur->nxt_len[cl];
  38. cur=cur->nxt[cl];
  39. }
  40. cl--;
  41. }
  42. return cur->nxt[0];
  43. }
  44.  
  45. void insert(node *r,int x)
  46. {
  47. node *it=new node(x);
  48. int cl=0;
  49. int c_len=1;
  50. do
  51. {
  52. if(cl==begin->nxt.size())
  53. {
  54. begin->nxt.push_back(end);
  55. end ->prv.push_back(begin);
  56. begin->nxt_len.push_back(size+1);
  57. end ->prv_len.push_back(size+1);
  58. }
  59. while(cl==r->prv.size())
  60. {
  61. c_len+=r->nxt_len[cl-1];
  62. r=r->nxt[cl-1];
  63. }
  64. it->nxt.push_back(r);
  65. it->prv.push_back(r->prv[cl]);
  66. it->nxt_len.push_back(c_len);
  67. it->prv_len.push_back(r->prv_len[cl]-c_len+1);
  68. r->prv[cl]->nxt[cl]=it;
  69. r->prv[cl]->nxt_len[cl]=it->prv_len[cl];
  70. r->prv[cl]=it;
  71. r->prv_len[cl]=c_len;
  72. cl++;
  73. }
  74. while(rand()&1);
  75.  
  76. while(cl<begin->nxt.size())
  77. {
  78. while(cl==r->prv.size())
  79. r=r->nxt[cl-1];
  80. r->prv_len[cl]++;
  81. r->prv[cl]->nxt_len[cl]++;
  82. cl++;
  83. }
  84. size++;
  85. }
  86.  
  87. void insert(int x)
  88. {
  89. insert(find_by_order(x),x);
  90. }
  91.  
  92. void erase(node *it)
  93. {
  94. int cl=0;
  95. for(;cl<it->nxt.size();cl++)
  96. {
  97. it->nxt[cl]->prv_len[cl]=it->prv[cl]->nxt_len[cl]=it->prv_len[cl]+it->nxt_len[cl]-1;
  98. it->nxt[cl]->prv[cl]=it->prv[cl];
  99. it->prv[cl]->nxt[cl]=it->nxt[cl];
  100. }
  101. node *r=it->nxt[cl-1];
  102. for(;cl<begin->nxt.size();cl++)
  103. {
  104. while(cl==r->prv.size())
  105. r=r->nxt[cl-1];
  106. r->prv[cl]->nxt_len[cl]--;
  107. r->prv_len[cl]--;
  108. }
  109. delete it;
  110. size--;
  111. }
  112.  
  113. void erase_by_order(int x)
  114. {
  115. erase(find_by_order(x));
  116. }
  117.  
  118. int &at(int x)
  119. {
  120. return find_by_order(x)->num;
  121. }
  122. int &operator [](int x)
  123. {
  124. return at(x);
  125. }
  126. } me;
Compilation error #stdin compilation error #stdout 0s 0KB
stdin
Standard input is empty
compilation info
prog.cpp:9:9: error: ‘vector’ does not name a type
         vector<node*> nxt;
         ^
prog.cpp:10:9: error: ‘vector’ does not name a type
         vector<node*> prv;
         ^
prog.cpp:11:9: error: ‘vector’ does not name a type
         vector<int> nxt_len;
         ^
prog.cpp:12:9: error: ‘vector’ does not name a type
         vector<int> prv_len;
         ^
prog.cpp: In constructor ‘skip_list::skip_list()’:
prog.cpp:23:16: error: ‘struct skip_list::node’ has no member named ‘nxt’
         begin->nxt={  end};
                ^
prog.cpp:24:16: error: ‘struct skip_list::node’ has no member named ‘prv’
         end  ->prv={begin};
                ^
prog.cpp:25:16: error: ‘struct skip_list::node’ has no member named ‘nxt_len’
         begin->nxt_len=end->prv_len={1};
                ^
prog.cpp:25:29: error: ‘struct skip_list::node’ has no member named ‘prv_len’
         begin->nxt_len=end->prv_len={1};
                             ^
prog.cpp: In member function ‘skip_list::node* skip_list::find_by_order(int)’:
prog.cpp:31:23: error: ‘struct skip_list::node’ has no member named ‘nxt’
         int cl=begin->nxt.size();
                       ^
prog.cpp:35:27: error: ‘struct skip_list::node’ has no member named ‘nxt’
             while(cl<cur->nxt.size() && cx+cur->nxt_len[cl]<x)
                           ^
prog.cpp:35:49: error: ‘struct skip_list::node’ has no member named ‘nxt_len’
             while(cl<cur->nxt.size() && cx+cur->nxt_len[cl]<x)
                                                 ^
prog.cpp:37:26: error: ‘struct skip_list::node’ has no member named ‘nxt_len’
                 cx+=cur->nxt_len[cl];
                          ^
prog.cpp:38:26: error: ‘struct skip_list::node’ has no member named ‘nxt’
                 cur=cur->nxt[cl];
                          ^
prog.cpp:42:21: error: ‘struct skip_list::node’ has no member named ‘nxt’
         return cur->nxt[0];
                     ^
prog.cpp: In member function ‘void skip_list::insert(skip_list::node*, int)’:
prog.cpp:52:27: error: ‘struct skip_list::node’ has no member named ‘nxt’
             if(cl==begin->nxt.size())
                           ^
prog.cpp:54:24: error: ‘struct skip_list::node’ has no member named ‘nxt’
                 begin->nxt.push_back(end);
                        ^
prog.cpp:55:24: error: ‘struct skip_list::node’ has no member named ‘prv’
                 end  ->prv.push_back(begin);
                        ^
prog.cpp:56:24: error: ‘struct skip_list::node’ has no member named ‘nxt_len’
                 begin->nxt_len.push_back(size+1);
                        ^
prog.cpp:57:24: error: ‘struct skip_list::node’ has no member named ‘prv_len’
                 end  ->prv_len.push_back(size+1);
                        ^
prog.cpp:59:26: error: ‘struct skip_list::node’ has no member named ‘prv’
             while(cl==r->prv.size())
                          ^
prog.cpp:61:27: error: ‘struct skip_list::node’ has no member named ‘nxt_len’
                 c_len+=r->nxt_len[cl-1];
                           ^
prog.cpp:62:22: error: ‘struct skip_list::node’ has no member named ‘nxt’
                 r=r->nxt[cl-1];
                      ^
prog.cpp:64:17: error: ‘struct skip_list::node’ has no member named ‘nxt’
             it->nxt.push_back(r);
                 ^
prog.cpp:65:17: error: ‘struct skip_list::node’ has no member named ‘prv’
             it->prv.push_back(r->prv[cl]);
                 ^
prog.cpp:65:34: error: ‘struct skip_list::node’ has no member named ‘prv’
             it->prv.push_back(r->prv[cl]);
                                  ^
prog.cpp:66:17: error: ‘struct skip_list::node’ has no member named ‘nxt_len’
             it->nxt_len.push_back(c_len);
                 ^
prog.cpp:67:17: error: ‘struct skip_list::node’ has no member named ‘prv_len’
             it->prv_len.push_back(r->prv_len[cl]-c_len+1);
                 ^
prog.cpp:67:38: error: ‘struct skip_list::node’ has no member named ‘prv_len’
             it->prv_len.push_back(r->prv_len[cl]-c_len+1);
                                      ^
prog.cpp:68:16: error: ‘struct skip_list::node’ has no member named ‘prv’
             r->prv[cl]->nxt[cl]=it;
                ^
prog.cpp:69:16: error: ‘struct skip_list::node’ has no member named ‘prv’
             r->prv[cl]->nxt_len[cl]=it->prv_len[cl];
                ^
prog.cpp:69:41: error: ‘struct skip_list::node’ has no member named ‘prv_len’
             r->prv[cl]->nxt_len[cl]=it->prv_len[cl];
                                         ^
prog.cpp:70:16: error: ‘struct skip_list::node’ has no member named ‘prv’
             r->prv[cl]=it;
                ^
prog.cpp:71:16: error: ‘struct skip_list::node’ has no member named ‘prv_len’
             r->prv_len[cl]=c_len;
                ^
prog.cpp:74:20: error: ‘rand’ was not declared in this scope
         while(rand()&1);
                    ^
prog.cpp:76:25: error: ‘struct skip_list::node’ has no member named ‘nxt’
         while(cl<begin->nxt.size())
                         ^
prog.cpp:78:26: error: ‘struct skip_list::node’ has no member named ‘prv’
             while(cl==r->prv.size())
                          ^
prog.cpp:79:22: error: ‘struct skip_list::node’ has no member named ‘nxt’
                 r=r->nxt[cl-1];
                      ^
prog.cpp:80:16: error: ‘struct skip_list::node’ has no member named ‘prv_len’
             r->prv_len[cl]++;
                ^
prog.cpp:81:16: error: ‘struct skip_list::node’ has no member named ‘prv’
             r->prv[cl]->nxt_len[cl]++;
                ^
prog.cpp: In member function ‘void skip_list::erase(skip_list::node*)’:
prog.cpp:95:21: error: ‘struct skip_list::node’ has no member named ‘nxt’
         for(;cl<it->nxt.size();cl++)
                     ^
prog.cpp:97:17: error: ‘struct skip_list::node’ has no member named ‘nxt’
             it->nxt[cl]->prv_len[cl]=it->prv[cl]->nxt_len[cl]=it->prv_len[cl]+it->nxt_len[cl]-1;
                 ^
prog.cpp:97:42: error: ‘struct skip_list::node’ has no member named ‘prv’
             it->nxt[cl]->prv_len[cl]=it->prv[cl]->nxt_len[cl]=it->prv_len[cl]+it->nxt_len[cl]-1;
                                          ^
prog.cpp:97:67: error: ‘struct skip_list::node’ has no member named ‘prv_len’
             it->nxt[cl]->prv_len[cl]=it->prv[cl]->nxt_len[cl]=it->prv_len[cl]+it->nxt_len[cl]-1;
                                                                   ^
prog.cpp:97:83: error: ‘struct skip_list::node’ has no member named ‘nxt_len’
             it->nxt[cl]->prv_len[cl]=it->prv[cl]->nxt_len[cl]=it->prv_len[cl]+it->nxt_len[cl]-1;
                                                                                   ^
prog.cpp:98:17: error: ‘struct skip_list::node’ has no member named ‘nxt’
             it->nxt[cl]->prv[cl]=it->prv[cl];
                 ^
prog.cpp:98:38: error: ‘struct skip_list::node’ has no member named ‘prv’
             it->nxt[cl]->prv[cl]=it->prv[cl];
                                      ^
prog.cpp:99:17: error: ‘struct skip_list::node’ has no member named ‘prv’
             it->prv[cl]->nxt[cl]=it->nxt[cl];
                 ^
prog.cpp:99:38: error: ‘struct skip_list::node’ has no member named ‘nxt’
             it->prv[cl]->nxt[cl]=it->nxt[cl];
                                      ^
prog.cpp:101:21: error: ‘struct skip_list::node’ has no member named ‘nxt’
         node *r=it->nxt[cl-1];
                     ^
prog.cpp:102:24: error: ‘struct skip_list::node’ has no member named ‘nxt’
         for(;cl<begin->nxt.size();cl++)
                        ^
prog.cpp:104:26: error: ‘struct skip_list::node’ has no member named ‘prv’
             while(cl==r->prv.size())
                          ^
prog.cpp:105:22: error: ‘struct skip_list::node’ has no member named ‘nxt’
                 r=r->nxt[cl-1];
                      ^
prog.cpp:106:16: error: ‘struct skip_list::node’ has no member named ‘prv’
             r->prv[cl]->nxt_len[cl]--;
                ^
prog.cpp:107:16: error: ‘struct skip_list::node’ has no member named ‘prv_len’
             r->prv_len[cl]--;
                ^
stdout
Standard output is empty