oj.uz

Submission #761551

# Submission time Handle Problem Language Result Execution time Memory
761551 2023-06-20T01:47:30 Z jajceslav Dancing Elephants (IOI11_elephants) C++17
100 / 100
 2025 ms 48316 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;
    }
};

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 102 ms 5052 KB Output is correct
8 Correct 109 ms 6512 KB Output is correct
9 Correct 260 ms 16176 KB Output is correct
10 Correct 164 ms 15956 KB Output is correct
11 Correct 171 ms 15844 KB Output is correct
12 Correct 427 ms 15436 KB Output is correct
13 Correct 183 ms 15724 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 102 ms 5052 KB Output is correct
8 Correct 109 ms 6512 KB Output is correct
9 Correct 260 ms 16176 KB Output is correct
10 Correct 164 ms 15956 KB Output is correct
11 Correct 171 ms 15844 KB Output is correct
12 Correct 427 ms 15436 KB Output is correct
13 Correct 183 ms 15724 KB Output is correct
14 Correct 233 ms 7384 KB Output is correct
15 Correct 201 ms 8656 KB Output is correct
16 Correct 538 ms 16124 KB Output is correct
17 Correct 665 ms 21580 KB Output is correct
18 Correct 674 ms 21328 KB Output is correct
19 Correct 254 ms 22500 KB Output is correct
20 Correct 649 ms 21544 KB Output is correct
21 Correct 703 ms 21336 KB Output is correct
22 Correct 266 ms 21840 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 102 ms 5052 KB Output is correct
8 Correct 109 ms 6512 KB Output is correct
9 Correct 260 ms 16176 KB Output is correct
10 Correct 164 ms 15956 KB Output is correct
11 Correct 171 ms 15844 KB Output is correct
12 Correct 427 ms 15436 KB Output is correct
13 Correct 183 ms 15724 KB Output is correct
14 Correct 233 ms 7384 KB Output is correct
15 Correct 201 ms 8656 KB Output is correct
16 Correct 538 ms 16124 KB Output is correct
17 Correct 665 ms 21580 KB Output is correct
18 Correct 674 ms 21328 KB Output is correct
19 Correct 254 ms 22500 KB Output is correct
20 Correct 649 ms 21544 KB Output is correct
21 Correct 703 ms 21336 KB Output is correct
22 Correct 266 ms 21840 KB Output is correct
23 Correct 1272 ms 48316 KB Output is correct
24 Correct 1290 ms 48296 KB Output is correct
25 Correct 1002 ms 48196 KB Output is correct
26 Correct 526 ms 48196 KB Output is correct
27 Correct 556 ms 48016 KB Output is correct
28 Correct 704 ms 6156 KB Output is correct
29 Correct 712 ms 6096 KB Output is correct
30 Correct 712 ms 6084 KB Output is correct
31 Correct 707 ms 6092 KB Output is correct
32 Correct 583 ms 47560 KB Output is correct
33 Correct 431 ms 46904 KB Output is correct
34 Correct 540 ms 47948 KB Output is correct
35 Correct 453 ms 48080 KB Output is correct
36 Correct 750 ms 40524 KB Output is correct
37 Correct 1661 ms 48044 KB Output is correct
38 Correct 605 ms 46912 KB Output is correct
39 Correct 568 ms 47772 KB Output is correct
40 Correct 611 ms 46796 KB Output is correct
41 Correct 2025 ms 45896 KB Output is correct
42 Correct 2013 ms 46116 KB Output is correct