Submission #373833

#	Time	Username	Problem	Language	Result	Execution time	Memory
373833		Bench0310	Dancing Elephants (IOI11_elephants)	C++17	100 / 100	2334 ms	48108 KiB

elephants

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

struct Node;
using twoNodes=array<Node*,2>;

struct Node
{
    int val;
    int sum;
    twoNodes kids;
    Node *p;
    Node *pathp;
    Node(int a){val=sum=a;kids[0]=kids[1]=p=pathp=nullptr;}
};

int side(Node *me){return (me->p?(me->p->kids[1]==me):0);}

void recalc(Node *me)
{
    if(!me) return;
    me->sum=me->val;
    for(Node *to:me->kids) if(to) me->sum+=to->sum;
}

void make_parent(Node *me,int id,Node *kid)
{
    if(me) me->kids[id]=kid;
    recalc(me);
    if(kid) kid->p=me;
}

void unmake_parent(Node *me,int id)
{
    make_parent(nullptr,0,me->kids[id]);
    make_parent(me,id,nullptr);
}

void rotate_up(Node *me)
{
    Node *p=me->p;
    int id=side(me);
    if(!p->p) swap(me->pathp,p->pathp);
    make_parent(p->p,side(p),me);
    make_parent(p,id,me->kids[id^1]);
    make_parent(me,id^1,p);
}

void splay(Node *me)
{
    while(me->p)
    {
        if(me->p->p)
        {
            if(side(me)==side(me->p)) rotate_up(me->p);
            else rotate_up(me);
        }
        rotate_up(me);
    }
    recalc(me);
}

void detach_path(Node *me)
{
    if(me->kids[1]) me->kids[1]->pathp=me;
    unmake_parent(me,1);
}

Node* access(Node *me)
{
    Node *up=me;
    splay(me);
    detach_path(me);
    while(me->pathp)
    {
        up=me->pathp;
        me->pathp=nullptr;
        splay(up);
        detach_path(up);
        make_parent(up,1,me);
        splay(me);
    }
    return up;
}

void cut(Node *me)
{
    access(me);
    unmake_parent(me,0);
}

void link(Node *me,Node *up)
{
    access(me);
    access(up);
    make_parent(me,0,up);
}

int query(Node *me)
{
    access(me);
    return me->sum;
}

const int inf=2000000005;
int n,l;
vector<int> x;
vector<Node*> v;
set<array<int,3>> both; //x,col,id
set<array<int,3>> white;

array<int,3> rep(int a,int c)
{
    return {(a!=0?(x[a]+c*l):(c*inf)),c,a};
}

Node* node(int a,int c)
{
    if(a==0) return v[c==1];
    else return v[2*a+c];
}

bool is_white(int a,int c)
{
    return (a==0||c==1);
}

void add_set(int a,int c)
{
    both.insert(rep(a,c));
    if(is_white(a,c)) white.insert(rep(a,c));
}

void rm_set(int a,int c)
{
    both.erase(rep(a,c));
    if(is_white(a,c)) white.erase(rep(a,c));
}

array<int,2> prv_white(int a,int c)
{
    auto it=white.lower_bound(rep(a,c));
    it--;
    return {(*it)[2],(*it)[1]};
}

array<int,2> nxt(int a,int c)
{
    auto it=both.find(rep(a,c));
    it++;
    return {(*it)[2],(*it)[1]};
}

void connect(int a,int c)
{
    auto it=both.upper_bound(rep(a,c));
    link(node(a,c),node((*it)[2],(*it)[1]));
}

void add(int a)
{
    add_set(a,0);
    add_set(a,1);
    link(node(a,0),node(a,1));
    auto [na,nc]=nxt(a,1);
    link(node(a,1),node(na,nc));
    auto [xa,xc]=prv_white(a,0);
    auto [ya,yc]=prv_white(a,1);
    bool diff=(xa!=ya||xc!=yc);
    cut(node(xa,xc));
    if(diff) cut(node(ya,yc));
    connect(xa,xc);
    if(diff) connect(ya,yc);
}

void rm(int a)
{
    cut(node(a,1));
    cut(node(a,0));
    auto [xa,xc]=prv_white(a,0);
    auto [ya,yc]=prv_white(a,1);
    bool diff=(xa!=ya||xc!=yc);
    cut(node(xa,xc));
    if(diff) cut(node(ya,yc));
    rm_set(a,0);
    rm_set(a,1);
    connect(xa,xc);
    if(diff) connect(ya,yc);
}

void init(int nn,int nl,int *nx)
{
    n=nn;
    l=nl;
    x.assign(n+1,0);
    for(int i=1;i<=n;i++) x[i]=nx[i-1];
    v.assign(2*n+2,nullptr);
    v[0]=new Node(0);
    v[1]=new Node(0);
    for(int i=1;i<=n;i++)
    {
        v[2*i]=new Node(1);
        v[2*i+1]=new Node(0);
    }
    link(v[0],v[1]);
    add_set(0,-1);
    add_set(0,1);
    for(int i=1;i<=n;i++) add(i);
}

int update(int a,int y)
{
    a++;
    rm(a);
    x[a]=y;
    add(a);
    return query(v[0]);
}

//int main()
//{
//    ios::sync_with_stdio(0);
//    cin.tie(0);
//    init(4,10,{10,15,17,20});
//    cout << update(2,16) << endl;
//    cout << update(1,25) << endl;
//    cout << update(3,35) << endl;
//    cout << update(0,38) << endl;
//    cout << update(2,0) << endl;
//    return 0;
//}

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