Submission #761551

#	Time	Username	Problem	Language	Result	Execution time	Memory
761551		jajceslav	Dancing Elephants (IOI11_elephants)	C++17	100 / 100	2025 ms	48316 KiB

elephants

#include "elephants.h"
#include<bits/stdc++.h>

using namespace std;

#define fi first
#define se second

const int MAXN = 150005;

/// link-cut node

struct node
{
    node *l, *r, *p;
    int val, sum, psh;
    int ind;

    node()
    {
        l = r = p = 0;
        val = sum = 0;
        psh = -1;
    }
    node(int vl)
    {
        l = r = p = 0;
        val = sum = vl;
        psh = -1;
    }
};

inline void Set(node *v, int val)
{
    if(!v) return;
    v->psh = v->val = val;
}

inline void push(node *v)
{
    if(!v)
        return;
    if(v->psh != -1)
    {
        Set(v->l, v->psh);
        Set(v->r, v->psh);
        v->psh = -1;
    }
}

inline int get(node *v)
{
    if(!v) return 0;
    return v->sum;
}

inline void upd(node *v)
{
    if(!v) return;

    push(v);
    v->sum = get(v->l) + v->val + get(v->r);
}

inline bool is_root(node *v)
{
    if(!v) return 0;
    if(!v->p) return 1;
    return (v->p->l != v) && (v->p->r != v);
}

vector<node*> lct;

inline void Init(int n)
{
    lct = vector<node*>(n);
    for(int i = 0; i < n; i++)
    {
        lct[i] = new node(1);
        lct[i]->ind = i;
    }
}

inline node* new_node(int val)
{
    node *nw = new node(val);
    lct.push_back(nw);
    return nw;
}

inline void rot(node *v)
{
    if(!v || is_root(v)) return;

    node *p = v->p;
    push(p);
    push(v);
    if(!is_root(p))
    {
        node *g = p->p;
        if(g->l == p) g->l = v;
        else g->r = v;
    }
    if(p->l == v)
    {
        p->l = v->r;
        if(p->l) p->l->p = p;
        v->r = p;
    }
    else
    {
        p->r = v->l;
        if(p->r) p->r->p = p;
        v->l = p;
    }

    v->p = p->p;
    p->p = v;

    upd(p);
    upd(v);
}

inline void splay(node *v)
{
    if(!v) return;
    while(!is_root(v))
    {
        node *p = v->p;
        node *g = p->p;
        if(!is_root(p))
        {
            if((g->l == p) == (p->l == v)) rot(p);
            else rot(v);
        }
        rot(v);
    }
    push(v);
}

inline void access(int i)
{
    node *v = lct[i], *c = v, *lst = 0;
    while(c)
    {
        splay(c);
        c->r = lst;
        upd(c);
        lst = c;
        c = c->p;
    }
    splay(v);
}

inline void link(int a, int b)
{
//    cout << "link " << a << ' ' << b << endl;
    access(a);
    access(b);
    node *u = lct[a], *v = lct[b];
    u->p = v;
}

inline void cut(int a)
{
//    cout << "cut " << a << endl;
    access(a);
    node *v = lct[a];
    if(v->l)
    {
        v->l->p = 0;
        v->l = 0;
        upd(v);
    }
}

inline int get_sum(int a)
{
    access(a);
    node *v = lct[a];
    return get(v->l);
}

int len, n;
set<pair<int, int> > st, hds;
int pos[MAXN];
int rc[MAXN], lc[MAXN];
vector<node*> spl;

inline int get_next(int i)
{
//    cout << "get_next(" << i << ")" << endl;
    if(i == -1)
        return -1;
    node *v = spl[i];
    splay(v);
    return v->val;
}

inline node* find_right(node *v)
{
//    cout << "find_right " << v << endl;
    while(v->r)
        v = v->r;
//    cout << "complete" << endl;
    return v;
}

inline node* find_left(node *v)
{
    while(v->l)
        v = v->l;
    return v;
}

inline void insert(int i, int l)
{
    if(l == -1)
    {
        splay(spl[n-1]);
        node *u = find_left(spl[n-1]);

        splay(u);
        node *v = spl[i];
        u->l = v;
        v->p = u;
//        cout << "special insert " << i << ' ' << l << endl;
        return;
    }
    node *u = spl[l], *v = spl[i];
    splay(u);
    if(u->r)
    {
        v->r = u->r;
        u->r->p = v;
    }
    u->r = v;
    v->p = u;
//    cout << "insert " << i << ' ' << l << endl;
}

void prnt();

inline void rem(int i)
{
//    cout << "rem " << i << endl;
    node *v = spl[i];
    splay(v);
    node *r = v->r;
    if(v->l)
    {
        v->l->p = 0;
        node *l = find_right(v->l);
        splay(l);
        l->r = r;
        if(r)
            r->p = l;
    }
    else
    {
        if(r)
            r->p = 0;
    }

    v->l = v->r = v->p = 0;
    v->sum = v->val = 0;

//    cout << "REMOVED " << i << endl;
    prnt();
}

inline void set_next(int l, int r, int val)
{
//    cout << "set_next " << l << ' ' << r << endl;
    node *u = spl[l], *v = spl[r];

    splay(u);
    node *lc = u->l;
    if(lc)
    {
        u->l = 0;
        lc->p = 0;
    }

    splay(v);
    v->val = val;
    Set(v->l, val);

    splay(u);
    u->l = lc;
    if(u->l)
        u->l->p = u;
}

inline void init_splay(int n)
{
    spl = vector<node*>(n);
    for(int i = 0; i < n; i++)
    {
        spl[i] = new node();
        spl[i]->ind = i;
    }
}

inline void connect(int i)
{
    auto it = st.lower_bound({pos[i], i});
    int l = -1, r = -1;
    if(it != st.begin())
    {
        auto pr = it; pr--;
        l = pr->se;

        rc[l] = i;
    }
    auto nx = it; nx++;
    if(nx == st.end())
    {
        lc[i] = rc[i] = -1;
        set_next(i, i, -1);
        return;
    }
    r = nx->se;
    lc[r] = i;

    lc[i] = l; rc[i] = r;
//    cout << i << " left: " << l << " right: " << r << endl;
    insert(i, l);


    if(l != -1)
    {
        if(get_next(l) == get_next(r))
        {
            cut(n+l);
            hds.erase({pos[l], l});
        }
    }
    auto cn = st.lower_bound({pos[i]+len+1, -1});
    set_next(i, i, cn->se);

    if(get_next(r) == get_next(i))
    {
        link(i+n, r+n);
    }
    else
    {
        link(i+n, get_next(i));
        hds.insert({pos[i], i});
    }

    if(get_next(l) == get_next(i))
    {
        if(get_next(l) != get_next(r))
        {
            cut(l+n);
            hds.erase({pos[l], l});
        }
        link(l+n, i+n);
    }
}

inline void disconnect(int i)
{
    cut(i+n);
    hds.erase({pos[i], i});

    if(lc[i] != -1 && get_next(i) == get_next(lc[i]))
    {
        cut(lc[i]+n);
        hds.erase({pos[lc[i]], lc[i]});
        if(get_next(lc[i]) == get_next(rc[i]))
        {
//            cout << "same" << endl;
            link(lc[i]+n, rc[i]+n);
        }
        else
        {
//            cout << "diff" << endl;
            link(lc[i]+n, get_next(lc[i]));
            hds.insert({pos[lc[i]], lc[i]});
        }
    }


}

inline void segment_add(int i)
{
    int lp = 0, rp = pos[i]-len-1;
    if(lc[i] != -1)
    {
        lp = pos[lc[i]]-len;
    }

//    cout << "add " << lp << ' ' << rp << endl;

    auto li = st.lower_bound({lp, -1});
    auto ri = st.lower_bound({rp, 1000000000});
    if(ri == st.begin())
        return;

    ri--;
    if(li->fi > ri->fi)
        return;

    int l = li->se, r = ri->se;
//    cout << "add idx " << l << ' ' << r << endl;
    if(lc[l] != -1 && get_next(lc[l]) == get_next(l))
    {
        cut(lc[l]+n);
        link(lc[l]+n, get_next(lc[l]));
        hds.insert({pos[lc[i]], lc[i]});
    }
    cut(r+n);
    link(r+n, i);
    hds.insert({pos[r], r});

    set_next(l, r, i);
}

inline void segment_rem(int i, int nxt)
{
    int lp = 0, rp = pos[i]-len-1;
    if(lc[i] != -1)
    {
        lp = pos[lc[i]]-len;
    }

    auto li = st.lower_bound({lp, -1});
    auto ri = st.lower_bound({rp, 1000000000});
    if(ri == st.begin())
        return;

    ri--;
    if(li->fi > ri->fi)
        return;

    int l = li->se, r = ri->se;
    set_next(l, r, nxt);

//    cout << "seg_rem " << l << ' ' << r << endl;
    cut(r+n);
    hds.erase({pos[r], r});
//    cout << "checking " << r << ": " << get_next(r) << ' ' << rc[r] << ": " << get_next(rc[r]) << endl;
    if(rc[r] != -1 && get_next(rc[r]) == get_next(r))
    {
        link(r+n, rc[r]+n);
    }
    else
    {
        link(r+n, nxt);
        hds.insert({pos[r], r});
    }


}

inline void add(int ps, int i)
{
    pos[i] = ps;
    st.insert({ps, i});

    connect(i);
//    cout << "connect " << i << endl;
    segment_add(i);
//    cout << "segment_add " << i << endl;
}

inline void remv(int i)
{
    int ps = pos[i];
    disconnect(i);
     int l = lc[i], r = rc[i];
    if(l != -1)
        rc[l] = r;
    lc[r] = l;
//    cout << "disconnect " << i << endl;
    segment_rem(i, rc[i]);
//    cout << "segment_rem " << i << endl;
    rem(i);


//    cout << "rem " << i << endl;
    st.erase({ps, i});
}

int getind(node *v)
{
    if(!v) return -1;
    return v->ind;
}

void prnt()
{
//    for(int i = 0;  i< n*2; i++)
//    {
//        cout << i << ": " << getind(lct[i]->p) << ' ' << getind(lct[i]->l) << ' ' << getind(lct[i]->r) << endl;
//    }
//    cout << endl;
//    for(int i = 0; i < n; i++)
//    {
//        cout << i << ": " << getind(spl[i]->p) << ' ' << getind(spl[i]->l) << ' ' << getind(spl[i]->r) << endl;
//    }
//    cout << "-------------" << endl;
}

void init(int N, int L, int X[])
{
    n = N+1;
    len = L;
    Init(n*2);
//    cout << "init" << endl;
    for(int i = 0; i < n; i++)
    {
      lct[i+n]->val = 0;
      upd(lct[i+n]);
    }
    for(int i = 0; i < n; i++)
    {
        link(i, i+n);
    }
    init_splay(n);
//    cout << "init splay" << endl;

    add(2e9, n-1);
    for(int i = 0; i < n-1; i++)
    {
        prnt();
      add(X[i], i);
    }
    prnt();
}



int update(int i, int y)
{
//    cout << "upd " << i << ' ' << y << endl;

    remv(i);
    add(y, i);

    prnt();

    int bg = st.begin()->se;
    access(bg);
    node *v = lct[bg];
    int res = v->val + get(v->l);

    return res-1;
}

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3