Submission #760849

# Submission time Handle Problem Language Result Execution time Memory
760849 2023-06-18T17:32:09 Z jajceslav Dancing Elephants (IOI11_elephants) C++17
0 / 100
0 ms 340 KB
#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;
    }
};

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

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

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

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

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

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;

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

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

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);
}

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);
}

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);
}

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

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

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

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

int get_next(int i)
{
    if(i == -1)
        return -1;
    node *v = spl[i];
    splay(v);
    return v->val;
}

node* find_right(node *v)
{
    while(v->r)
        v = v->r;
    return v;
}

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

void insert(int i, int l)
{
    if(l == -1)
    {
        node *u = 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 rem(int i)
{
    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;
}

void set_next(int l, int r, int val)
{
    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 = 0;
}

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

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;
    insert(i, l);


    if(l != -1)
    {
        if(get_next(l) == get_next(r))
        {
            cut(n+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));
    }

    if(get_next(l) == get_next(i))
    {
        if(get_next(l) != get_next(r))
            cut(l+n);
        link(l+n, i+n);
    }
}

void disconnect(int i)
{
    cut(i+n);

    if(lc[i] != -1 && get_next(i) == get_next(lc[i]))
    {
        cut(lc[i]+n);
        if(get_next(lc[i]) == get_next(rc[i]))
        {
            link(lc[i]+n, rc[i]+n);
        }
        else
        {
            link(lc[i]+n, get_next(lc[i]));
        }
    }
}

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 << '\n';

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

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

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

    set_next(l, r, i);
}

void segment_rem(int i)
{
    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, -1});
    if(ri == st.begin())
        return;

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

    int l = li->se, r = ri->se;
    cut(r+n);
    if(rc[r] != -1 && get_next(rc[r]) == get_next(r))
    {
        link(r+n, rc[r]+n);
    }
    else
    {
        link(r+n, rc[i]);
    }

    set_next(l, r, rc[i]);
}

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;
}

void remv(int i)
{
    int ps = pos[i];
    disconnect(i);
//    cout << "disconnect " << i << endl;
    segment_rem(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) << '\n';
//    }
//    cout << '\n';
}

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++)
    {
      add(X[i], i);
    }
}

int update(int i, int y)
{
    return 1;

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

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

    return res-1;
}
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -