fork download

copy

const int INF=2e9;
 
struct skip_list
{
    struct node
    {
        int num;
        vector<node*> nxt;
        vector<node*> prv;
        vector<int> nxt_len;
        vector<int> prv_len;
        node(int x):num(x){}
    } *begin,*end;
 
    int size;
 
    skip_list()
    {
        size=0;
        begin=new node(-INF);
        end  =new node(+INF);
        begin->nxt={  end};
        end  ->prv={begin};
        begin->nxt_len=end->prv_len={1};
    }
 
    node *find(int x)
    {
        node *cur=begin;
        int cl=begin->nxt.size();
        while(cl>=0)
        {
            while(cl<cur->nxt.size() && cur->nxt[cl]->num<x)
            	cur=cur->nxt[cl];
            cl--;
        }
        return cur->nxt[0];
    }
 
    node *find_by_order(int x)
    {
        node *cur=begin;
        int cl=begin->nxt.size();
        int cx=-1;
        while(cl>=0)
        {
            while(cl<cur->nxt.size() && cx+cur->nxt_len[cl]<x)
            {
                cx+=cur->nxt_len[cl];
                cur=cur->nxt[cl];
            }
            cl--;
        }
        return cur->nxt[0];
    }
 
    int order_of_key(int x)
    {
    {
        node *cur=begin;
        int cl=begin->nxt.size();
        int cx=0;
        while(cl>=0)
        {
            while(cl<cur->nxt.size() && cur->nxt[cl]->num<x)
            {
                cx+=cur->nxt_len[cl];
                cur=cur->nxt[cl];
            }
            cl--;
        }
        return cx;
    }
 
    }
 
    void insert(node *r,int x)
    {
        node *it=new node(x);
        int cl=0;
        int c_len=1;
        do
        {
            if(cl==begin->nxt.size())
            {
                begin->nxt.push_back(end);
                end  ->prv.push_back(begin);
                begin->nxt_len.push_back(size+1);
                end  ->prv_len.push_back(size+1);
            }
            while(cl==r->prv.size())
            {
                c_len+=r->nxt_len[cl-1];
                r=r->nxt[cl-1];
            }
            it->nxt.push_back(r);
            it->prv.push_back(r->prv[cl]);
            it->nxt_len.push_back(c_len);
            it->prv_len.push_back(r->prv_len[cl]-c_len+1);
            r->prv[cl]->nxt[cl]=it;
            r->prv[cl]->nxt_len[cl]=it->prv_len[cl];
            r->prv[cl]=it;
            r->prv_len[cl]=c_len;
            cl++;
        }
        while(rand()&1);
 
        while(cl<begin->nxt.size())
        {
            while(cl==r->prv.size())
                r=r->nxt[cl-1];
            r->prv_len[cl]++;
            r->prv[cl]->nxt_len[cl]++;
            cl++;
        }
        size++;
    }
 
    void insert(int x)
    {
    	insert(find(x),x);
    }
 
    void erase(node *it)
    {
        int cl=0;
        for(;cl<it->nxt.size();cl++)
        {
            it->nxt[cl]->prv_len[cl]=it->prv[cl]->nxt_len[cl]=it->prv_len[cl]+it->nxt_len[cl]-1;
            it->nxt[cl]->prv[cl]=it->prv[cl];
            it->prv[cl]->nxt[cl]=it->nxt[cl];
        }
        node *r=it->nxt[cl-1];
        for(;cl<begin->nxt.size();cl++)
        {
            while(cl==r->prv.size())
                r=r->nxt[cl-1];
            r->prv[cl]->nxt_len[cl]--;
            r->prv_len[cl]--;
        }
        delete it;
        size--;
    }
 
    void erase(int x)
    {
        erase(find(x));
    }
    void erase_by_order(int x)
    {
        erase(find_by_order(x));
    }
 
    int &at(int x)
    {
        return find_by_order(x)->num;
    }
    int &operator [](int x)
    {
        return at(x);
    }
} me;

prog.cpp:8:9: error: ‘vector’ does not name a type
         vector<node*> nxt;
         ^
prog.cpp:9:9: error: ‘vector’ does not name a type
         vector<node*> prv;
         ^
prog.cpp:10:9: error: ‘vector’ does not name a type
         vector<int> nxt_len;
         ^
prog.cpp:11:9: error: ‘vector’ does not name a type
         vector<int> prv_len;
         ^
prog.cpp: In constructor ‘skip_list::skip_list()’:
prog.cpp:22:16: error: ‘struct skip_list::node’ has no member named ‘nxt’
         begin->nxt={  end};
                ^
prog.cpp:23:16: error: ‘struct skip_list::node’ has no member named ‘prv’
         end  ->prv={begin};
                ^
prog.cpp:24:16: error: ‘struct skip_list::node’ has no member named ‘nxt_len’
         begin->nxt_len=end->prv_len={1};
                ^
prog.cpp:24: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(int)’:
prog.cpp:30:23: error: ‘struct skip_list::node’ has no member named ‘nxt’
         int cl=begin->nxt.size();
                       ^
prog.cpp:33:27: error: ‘struct skip_list::node’ has no member named ‘nxt’
             while(cl<cur->nxt.size() && cur->nxt[cl]->num<x)
                           ^
prog.cpp:33:46: error: ‘struct skip_list::node’ has no member named ‘nxt’
             while(cl<cur->nxt.size() && cur->nxt[cl]->num<x)
                                              ^
prog.cpp:34:23: error: ‘struct skip_list::node’ has no member named ‘nxt’
              cur=cur->nxt[cl];
                       ^
prog.cpp:37:21: error: ‘struct skip_list::node’ has no member named ‘nxt’
         return cur->nxt[0];
                     ^
prog.cpp: In member function ‘skip_list::node* skip_list::find_by_order(int)’:
prog.cpp:43:23: error: ‘struct skip_list::node’ has no member named ‘nxt’
         int cl=begin->nxt.size();
                       ^
prog.cpp:47:27: error: ‘struct skip_list::node’ has no member named ‘nxt’
             while(cl<cur->nxt.size() && cx+cur->nxt_len[cl]<x)
                           ^
prog.cpp:47: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:49:26: error: ‘struct skip_list::node’ has no member named ‘nxt_len’
                 cx+=cur->nxt_len[cl];
                          ^
prog.cpp:50:26: error: ‘struct skip_list::node’ has no member named ‘nxt’
                 cur=cur->nxt[cl];
                          ^
prog.cpp:54:21: error: ‘struct skip_list::node’ has no member named ‘nxt’
         return cur->nxt[0];
                     ^
prog.cpp: In member function ‘int skip_list::order_of_key(int)’:
prog.cpp:61:23: error: ‘struct skip_list::node’ has no member named ‘nxt’
         int cl=begin->nxt.size();
                       ^
prog.cpp:65:27: error: ‘struct skip_list::node’ has no member named ‘nxt’
             while(cl<cur->nxt.size() && cur->nxt[cl]->num<x)
                           ^
prog.cpp:65:46: error: ‘struct skip_list::node’ has no member named ‘nxt’
             while(cl<cur->nxt.size() && cur->nxt[cl]->num<x)
                                              ^
prog.cpp:67:26: error: ‘struct skip_list::node’ has no member named ‘nxt_len’
                 cx+=cur->nxt_len[cl];
                          ^
prog.cpp:68:26: error: ‘struct skip_list::node’ has no member named ‘nxt’
                 cur=cur->nxt[cl];
                          ^
prog.cpp: In member function ‘void skip_list::insert(skip_list::node*, int)’:
prog.cpp:84:27: error: ‘struct skip_list::node’ has no member named ‘nxt’
             if(cl==begin->nxt.size())
                           ^
prog.cpp:86:24: error: ‘struct skip_list::node’ has no member named ‘nxt’
                 begin->nxt.push_back(end);
                        ^
prog.cpp:87:24: error: ‘struct skip_list::node’ has no member named ‘prv’
                 end  ->prv.push_back(begin);
                        ^
prog.cpp:88:24: error: ‘struct skip_list::node’ has no member named ‘nxt_len’
                 begin->nxt_len.push_back(size+1);
                        ^
prog.cpp:89:24: error: ‘struct skip_list::node’ has no member named ‘prv_len’
                 end  ->prv_len.push_back(size+1);
                        ^
prog.cpp:91:26: error: ‘struct skip_list::node’ has no member named ‘prv’
             while(cl==r->prv.size())
                          ^
prog.cpp:93:27: error: ‘struct skip_list::node’ has no member named ‘nxt_len’
                 c_len+=r->nxt_len[cl-1];
                           ^
prog.cpp:94:22: error: ‘struct skip_list::node’ has no member named ‘nxt’
                 r=r->nxt[cl-1];
                      ^
prog.cpp:96:17: error: ‘struct skip_list::node’ has no member named ‘nxt’
             it->nxt.push_back(r);
                 ^
prog.cpp:97:17: error: ‘struct skip_list::node’ has no member named ‘prv’
             it->prv.push_back(r->prv[cl]);
                 ^
prog.cpp:97:34: error: ‘struct skip_list::node’ has no member named ‘prv’
             it->prv.push_back(r->prv[cl]);
                                  ^
prog.cpp:98:17: error: ‘struct skip_list::node’ has no member named ‘nxt_len’
             it->nxt_len.push_back(c_len);
                 ^
prog.cpp:99: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:99: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:100:16: error: ‘struct skip_list::node’ has no member named ‘prv’
             r->prv[cl]->nxt[cl]=it;
                ^
prog.cpp:101:16: error: ‘struct skip_list::node’ has no member named ‘prv’
             r->prv[cl]->nxt_len[cl]=it->prv_len[cl];
                ^
prog.cpp:101:41: error: ‘struct skip_list::node’ has no member named ‘prv_len’
             r->prv[cl]->nxt_len[cl]=it->prv_len[cl];
                                         ^
prog.cpp:102:16: error: ‘struct skip_list::node’ has no member named ‘prv’
             r->prv[cl]=it;
                ^
prog.cpp:103:16: error: ‘struct skip_list::node’ has no member named ‘prv_len’
             r->prv_len[cl]=c_len;
                ^
prog.cpp:106:20: error: ‘rand’ was not declared in this scope
         while(rand()&1);
                    ^
prog.cpp:108:25: error: ‘struct skip_list::node’ has no member named ‘nxt’
         while(cl<begin->nxt.size())
                         ^
prog.cpp:110:26: error: ‘struct skip_list::node’ has no member named ‘prv’
             while(cl==r->prv.size())
                          ^
prog.cpp:111:22: error: ‘struct skip_list::node’ has no member named ‘nxt’
                 r=r->nxt[cl-1];
                      ^
prog.cpp:112:16: error: ‘struct skip_list::node’ has no member named ‘prv_len’
             r->prv_len[cl]++;
                ^
prog.cpp:113: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:127:21: error: ‘struct skip_list::node’ has no member named ‘nxt’
         for(;cl<it->nxt.size();cl++)
                     ^
prog.cpp:129: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:129: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:129: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:129: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:130:17: error: ‘struct skip_list::node’ has no member named ‘nxt’
             it->nxt[cl]->prv[cl]=it->prv[cl];
                 ^
prog.cpp:130:38: error: ‘struct skip_list::node’ has no member named ‘prv’
             it->nxt[cl]->prv[cl]=it->prv[cl];
                                      ^
prog.cpp:131:17: error: ‘struct skip_list::node’ has no member named ‘prv’
             it->prv[cl]->nxt[cl]=it->nxt[cl];
                 ^
prog.cpp:131:38: error: ‘struct skip_list::node’ has no member named ‘nxt’
             it->prv[cl]->nxt[cl]=it->nxt[cl];
                                      ^
prog.cpp:133:21: error: ‘struct skip_list::node’ has no member named ‘nxt’
         node *r=it->nxt[cl-1];
                     ^
prog.cpp:134:24: error: ‘struct skip_list::node’ has no member named ‘nxt’
         for(;cl<begin->nxt.size();cl++)
                        ^
prog.cpp:136:26: error: ‘struct skip_list::node’ has no member named ‘prv’
             while(cl==r->prv.size())
                          ^
prog.cpp:137:22: error: ‘struct skip_list::node’ has no member named ‘nxt’
                 r=r->nxt[cl-1];
                      ^
prog.cpp:138:16: error: ‘struct skip_list::node’ has no member named ‘prv’
             r->prv[cl]->nxt_len[cl]--;
                ^
prog.cpp:139:16: error: ‘struct skip_list::node’ has no member named ‘prv_len’
             r->prv_len[cl]--;
                ^

Standard output is empty