oj.uz

Submission #397719

# Submission time Handle Problem Language Result Execution time Memory
397719 2021-05-02T23:10:09 Z jeroenodb Dancing Elephants (IOI11_elephants) C++14
100 / 100
 1932 ms 41284 KB 
#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.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 117 ms 4648 KB Output is correct
8 Correct 118 ms 5944 KB Output is correct
9 Correct 318 ms 13700 KB Output is correct
10 Correct 181 ms 13532 KB Output is correct
11 Correct 188 ms 13528 KB Output is correct
12 Correct 479 ms 13680 KB Output is correct
13 Correct 249 ms 13380 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 117 ms 4648 KB Output is correct
8 Correct 118 ms 5944 KB Output is correct
9 Correct 318 ms 13700 KB Output is correct
10 Correct 181 ms 13532 KB Output is correct
11 Correct 188 ms 13528 KB Output is correct
12 Correct 479 ms 13680 KB Output is correct
13 Correct 249 ms 13380 KB Output is correct
14 Correct 1896 ms 6616 KB Output is correct
15 Correct 1365 ms 7840 KB Output is correct
16 Correct 672 ms 14416 KB Output is correct
17 Correct 763 ms 19064 KB Output is correct
18 Correct 709 ms 19008 KB Output is correct
19 Correct 258 ms 19096 KB Output is correct
20 Correct 747 ms 19160 KB Output is correct
21 Correct 751 ms 19044 KB Output is correct
22 Correct 354 ms 18628 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 117 ms 4648 KB Output is correct
8 Correct 118 ms 5944 KB Output is correct
9 Correct 318 ms 13700 KB Output is correct
10 Correct 181 ms 13532 KB Output is correct
11 Correct 188 ms 13528 KB Output is correct
12 Correct 479 ms 13680 KB Output is correct
13 Correct 249 ms 13380 KB Output is correct
14 Correct 1896 ms 6616 KB Output is correct
15 Correct 1365 ms 7840 KB Output is correct
16 Correct 672 ms 14416 KB Output is correct
17 Correct 763 ms 19064 KB Output is correct
18 Correct 709 ms 19008 KB Output is correct
19 Correct 258 ms 19096 KB Output is correct
20 Correct 747 ms 19160 KB Output is correct
21 Correct 751 ms 19044 KB Output is correct
22 Correct 354 ms 18628 KB Output is correct
23 Correct 1315 ms 41168 KB Output is correct
24 Correct 1341 ms 41284 KB Output is correct
25 Correct 1122 ms 41280 KB Output is correct
26 Correct 528 ms 41156 KB Output is correct
27 Correct 481 ms 41048 KB Output is correct
28 Correct 717 ms 5956 KB Output is correct
29 Correct 692 ms 5984 KB Output is correct
30 Correct 716 ms 5980 KB Output is correct
31 Correct 696 ms 6084 KB Output is correct
32 Correct 577 ms 40520 KB Output is correct
33 Correct 543 ms 40004 KB Output is correct
34 Correct 569 ms 40804 KB Output is correct
35 Correct 845 ms 41092 KB Output is correct
36 Correct 1141 ms 40616 KB Output is correct
37 Correct 1704 ms 40900 KB Output is correct
38 Correct 826 ms 39812 KB Output is correct
39 Correct 570 ms 40820 KB Output is correct
40 Correct 817 ms 39880 KB Output is correct
41 Correct 1908 ms 40588 KB Output is correct
42 Correct 1932 ms 40840 KB Output is correct