Submission #192706

#	Time	Username	Problem	Language	Result	Execution time	Memory
192706		imeimi2000	Dancing Elephants (IOI11_elephants)	C++17	100 / 100	1704 ms	28344 KiB

elephants

#include <bits/stdc++.h>
#define fs first
#define se second
using namespace std;
typedef pair<int, int> pii;

const int inf = 1e9 + 1;
const int rinf = inf + inf;
const int linf = -1;

int n, l;

namespace LCT {
    struct node {
        int L, R, P;
        int cnt, sum;
    } ns[300010];
    void set_cnt(int x, int v) {
        ns[x].cnt = ns[x].sum = v;
    }
    void update(int x) {
        ns[x].sum = ns[x].cnt;
        if (ns[x].L) ns[x].sum += ns[ns[x].L].sum;
        if (ns[x].R) ns[x].sum += ns[ns[x].R].sum;
    }
    bool is_root(int x) {
        return ns[x].P == 0 || ns[ns[x].P].L != x && ns[ns[x].P].R != x;
    }
    void rotate(int x) {
        int p = ns[x].P;
        if (ns[p].L == x) {
            ns[p].L = ns[x].R;
            if (ns[p].L) ns[ns[p].L].P = p;
            ns[x].R = p;
        }
        else {
            ns[p].R = ns[x].L;
            if (ns[p].R) ns[ns[p].R].P = p;
            ns[x].L = p;
        }
        ns[x].P = ns[p].P;
        ns[p].P = x;
        if (ns[x].P) {
            if (ns[ns[x].P].L == p) ns[ns[x].P].L = x;
            else if (ns[ns[x].P].R == p) ns[ns[x].P].R = x;
        }
        update(p);
        update(x);
    }
    void splay(int x) {
        while (!is_root(x)) {
            int p = ns[x].P;
            if (!is_root(p)) {
                if ((ns[ns[p].P].L == p) == (ns[p].L == x)) rotate(p);
                else rotate(x);
            }
            rotate(x);
        }
    }
    int access(int x) {
        splay(x);
        ns[x].R = 0;
        update(x);
        int ret = x;
        while (ns[x].P) {
            ret = ns[x].P;
            splay(ret);
            ns[ret].R = x;
            update(ret);
            splay(x);
        }
        return ret;
    }
    void link(int x, int p) {
        access(x);
        access(p);
        ns[x].L = p;
        ns[p].P = x;
        update(x);
    }
    void cut(int x) {
        access(x);
        ns[ns[x].L].P = 0;
        ns[x].L = 0;
        update(x);
    }
    int get_sum(int x) {
        access(x);
        return ns[x].sum;
    }
    int par(int x) {
        access(x);
        x = ns[x].L;
        while (ns[x].R) x = ns[x].R;
        return x;
    }
}

int pos[150010];
set<pii> sp;
int dl, dr;

void init(int N, int L, int X[]) {
    n = N;
    l = L;
    dl = n + n + 1;
    pos[n + 1] = linf - l;
    dr = n + n + 2;
    pos[n + 2] = rinf - l;
    for (int i = 1; i <= n; ++i) {
        LCT::set_cnt(i, 1);
        pos[i] = X[i - 1];
        sp.emplace(pos[i], i);
        sp.emplace(pos[i] + l, i + n);
    }
    sp.emplace(linf, dl);
    sp.emplace(rinf, dr);
    pii prv = pii(-1, -1);
    for (pii i : sp) {
        if (prv.se != -1) {
            if (prv.se <= n) {
                LCT::link(prv.se, prv.se + n);
            }
            else {
                LCT::link(prv.se, i.se);
            }
        }
        prv = i;
    }
}

int update(int p, int v) {
    ++p;
    vector<int> need;
    need.push_back(p + n);
    auto it1 = prev(sp.find(pii(pos[p], p)));
    auto it2 = prev(sp.find(pii(pos[p] + l, p + n)));
    if (it1->se > n) need.push_back(it1->se);
    if (it2->se > n) need.push_back(it2->se);
    sp.erase(pii(pos[p], p));
    sp.erase(pii(pos[p] + l, p + n));
    pos[p] = v;
    sp.emplace(pos[p], p);
    sp.emplace(pos[p] + l, p + n);
    auto it3 = prev(sp.find(pii(pos[p], p)));
    auto it4 = prev(sp.find(pii(pos[p] + l, p + n)));
    if (it3->se > n) need.push_back(it3->se);
    if (it4->se > n) need.push_back(it4->se);
    sort(need.begin(), need.end());
    need.erase(unique(need.begin(), need.end()), need.end());
    for (int i : need) LCT::cut(i);
    for (int i : need) {
        int x = pos[i - n] + l;
        auto it = sp.upper_bound(pii(x, i));
        int p = it->se;
        LCT::link(i, p);
    }
    return LCT::get_sum(dl);
}

Compilation message (stderr)

elephants.cpp: In function 'bool LCT::is_root(int)':
elephants.cpp:27:51: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
         return ns[x].P == 0 || ns[ns[x].P].L != x && ns[ns[x].P].R != x;
                                ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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