Submission #397719

#	Time	Username	Problem	Language	Result	Execution time	Memory
397719		jeroenodb	Dancing Elephants (IOI11_elephants)	C++14	100 / 100	1932 ms	41284 KiB

elephants

#include "bits/stdc++.h"
#include "elephants.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;


template<class T> struct splaytree {
    #define l kid(b)
    #define r kid(b^1)
    #define L kid(0)
    #define R kid(1)
    struct node {
        T val;
        node *c[2] = {NULL,NULL}, *par =NULL;
        bool flip=false,pathtop=true;
        node(const T& v) : val(v) {}
        node*& kid(bool k) {return c[k^flip];}
        node() {}
    };
    static void push(node* at) {
        if(at->flip) {
            if(at->L) at->L->flip^=1;
            if(at->R) at->R->flip^=1;
            swap(at->L,at->R);
            at->flip=0;
        }
    }
    static void recalc(node* at) {
        at->val.recalc();
        if(at->L) at->val.recalc(at->L->val); 
        if(at->R) at->val.recalc(at->R->val);
    }
    static void print(node* n) {
        if(n==NULL) return;
        print(n->L);
        cout << n->val << ' ';
        print(n->R);
    }
    static void rotate(node* n) {
        // Precondition: n is not the root, Postcondition: rotates n to the place of its parent
        // assert(n and !n->pathtop and n->par);
        node* par = n->par;
        push(par);
        push(n);
        if(!par->pathtop) {
            auto gp = par->par;
            if(gp->L==par) gp->L=n;
            else if(gp->R==par) gp->R=n;
        }
        n->par = par->par;
        bool b= n!=par->L;
        par->l = n->r; // Fix right child of current node
        if(n->r) n->r->par = par;
        n->r = par; // Put parent under current node
        par->par = n;
        swap(par->pathtop, n->pathtop);
        recalc(par);
        recalc(n);
    }
    static void splay(node* n) {
        while(!n->pathtop) {
            if(n->par->pathtop) {
                rotate(n);
            } else {
                auto p = n->par, gp = p->par;
                // Double rotations
                if((p->L==n) == (gp->L==p)) {
                    rotate(p);
                } else {
                    rotate(n);
                }
                rotate(n);
            }
        }
        push(n);
    }
    #undef l
    #undef r
    #undef L
    #undef R
};

struct vertex{
    int sm=0, id;
    bool white=false;
    vertex(int idd, bool b){id=idd, white = b, sm=!b;}
    vertex(){}
    void recalc(const vertex& o) {
        sm += o.sm;
    }
    void recalc() {
        sm = !white;
    }
}; 
ostream& operator<<(ostream& c, const vertex& v) {
    return c << v.id << (v.white?"W ":"B ");
}
struct linkcut {
    // initially the linkcut tree consists of n disconnected size 1 trees.
    typedef splaytree<vertex> bst;
    typedef bst::node node;
    int n=0;
    node* t=NULL;
    linkcut() {}
    linkcut(int N) {
        n=N;
        t = new node[n+1];
        // for(int i=0;i<n;++i) {
        //     t[i] = node(vertex());
        // }
    }
    void add(int i, bool white) {
        int id = i;
        if(i>=n and i<2*n) i-=n;
        t[i] = node(vertex(id,white));
    }
    node* expose(int u) {
        node *at = NULL, *par = t+u;
        for(;par; at=par,par = par->par) {
            bst::splay(par);
            if(par->kid(1)) {
                par->kid(1)->pathtop = true;
                par->kid(1) = NULL;
            }
            if(at) at->pathtop = false;
            par->kid(1) = at;
            bst::recalc(par);     
        }
        bst::splay(t+u);
        return t+u;
    }
    void reroot(int u) {
        node* root = expose(u); 
        root->flip^=1;
    }
    void link(int u, int v) {
        reroot(u); 
        t[u].par = t+v;         // connect with unmarked edge
    }
    void cut(int u, int v) {
        reroot(u); expose(v);
        node* at = t+v;
        assert(at->kid(0) == t+u);
        if(at->kid(0)) {
            auto& prev = at->kid(0);

            prev->par=NULL;
            prev->pathtop = true;
            prev = NULL;
        }
        bst::recalc(at);
    }
    ll calc(int u, int v) {
        reroot(u);
        auto root = expose(v);
        // bst::print(root);
        return root->val.sm;
    }

};

int n,l;
map<pi,int> m;
linkcut lc;
vi xs;
void init(int N, int L, int X[]) {
    l=L;
    lc = linkcut(N*2+2);
    n = N;
    xs = vi(X,X+n);
    lc.add(n*2,true), lc.add(n*2+1,true);
    for(int i=0;i<n;++i) {
        int x = X[i];
        m[{x,i}] = i;
        m[{x+L,i+n}]= i+n;
        lc.add(i,false), lc.add(i+n,true);
        lc.link(i,i+n);
    }

    m[{-2*oo,n*2}] = n*2;
    m[{oo*2,n*2+1}] = n*2+1;
    for(int i=0;i<n;++i) {
        auto iter = m.upper_bound({X[i]+L,i+n});
        lc.link(i+n,iter->second);
    }
    auto iter = m.upper_bound({-2*oo+L,2*n});
    lc.link(n*2,iter->second);
}

int update(int i, int y) {
    int X = xs[i];
    // white node -> cut 
    lc.cut(i+n,m.upper_bound({X+l,i+n})->second);
    auto fix = [](int x, int j) {
        auto iter = m.find({x,j});
        auto maybe = prev(iter);
        m.erase(iter);
        if(maybe->second>=n) {
            // node is white and thus connected
            lc.cut(j, maybe->second);
            lc.link(maybe->second, next(maybe)->second);
        }
    };
    fix(X+l,i+n);
    fix(X,i);

    xs[i] = y;
    // debug(xs);
    auto fix2 = [](int x, int j) {
        auto iter = m.lower_bound({x,j});
        auto maybe = prev(iter);
        if(maybe->second>=n) {
            // node is white and thus connected
            lc.cut(maybe->second, next(maybe)->second);
            lc.link(maybe->second, j);

        }
        m[{x,j}] = j;
    };
    auto iter = m.upper_bound({y+l,i+n});
    lc.link(i+n,iter->second);
    fix2(y+l,i+n);
    fix2(y,i);
    return lc.calc(n*2,n*2+1);
}

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