Submission #996924

#	Time	Username	Problem	Language	Result	Execution time	Memory
996924		caterpillow	Dancing Elephants (IOI11_elephants)	C++17	100 / 100	2001 ms	79996 KiB

elephants

#include <bits/stdc++.h>
#include "elephants.h"

using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using ll = long long;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
#define vt vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end() 
#define size(x) ((int) (x).size())
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'
const ll INF = 1e18;
const int inf = 1e9;

random_device rd;
mt19937 mt(rd());

using ptr = struct Node*;
struct Node {
    int pri, sz, val, agg, lazy;
    ptr l, r, par;

    Node (int _v) {
        pri = mt();
        sz = 1;
        l = r = par = 0;
        val = agg = _v;
        lazy = 0;
    }
};

inline int sz(ptr n) { return n ? n->sz : 0; }
inline int agg(ptr n) { return n ? n->agg : -1; }

void push(ptr n) {
    if (!n) return;
    n->val += n->lazy;
    n->agg += n->lazy;
    if (n->l) n->l->lazy += n->lazy;
    if (n->r) n->r->lazy += n->lazy;
    n->lazy = 0;
}

ptr pull(ptr n) {
    if (!n) return n;
    push(n->l), push(n->r);
    n->sz = sz(n->l) + 1 + sz(n->r);
    n->agg = max({agg(n->l), n->val, agg(n->r)});
    if (n->l) n->l->par = n;
    if (n->r) n->r->par = n;
    return n;
}

pair<ptr, ptr> spliti(ptr n, int i) {
    if (!n) return {n, n};
    push(n);
    n->par = 0;
    if (i <= sz(n->l)) {
        auto [l, r] = spliti(n->l, i);
        n->l = r;
        return {l, pull(n)};
    } else {
        auto [l, r] = spliti(n->r, i - sz(n->l) - 1);
        n->r = l;
        return {pull(n), r};
    }
}

tuple<ptr, ptr, ptr> cut(ptr n, int lo, int hi) {
    auto [lhs, r] = spliti(n, hi + 1);
    auto [l, m] = spliti(lhs, lo);
    return {l, m, r};
}

ptr merge(ptr l, ptr r) {
    if (!l || !r) return l ? l : r;
    push(l), push(r);
    ptr t;
    if (l->pri > r->pri) l->r = merge(l->r, r), t = l;
    else r->l = merge(l, r->l), t = r;
    return pull(t);
}

void add(ptr n, int v) {
    if (!n) return;
    n->lazy += v;
    push(n);
}

int order(ptr n, ptr from = 0) {
    if (!n) return -1; // hack
    int res = order(n->par, n);
    if (from == n->r || !from) res += sz(n->l) + 1;
    return res;
}

void clean(ptr n) {
    if (!n) return;
    clean(n->par);
    push(n);
}

ll n, w;
set<pl> cows;
vt<ll> pos;
vt<pair<ptr, ptr>> loc; // {in, out}
ptr tour;

void erase(int u) {
    int in = order(loc[u].f);
    int out = order(loc[u].s);
    auto [l, mid, r] = cut(tour, in, out);
    auto [ml, m, mr] = cut(mid, 1, sz(mid) - 2);
    push(ml);
    add(m, -(ml->val) - 1);
    tour = merge(l, r);
    cows.erase({pos[u], u});
    auto it = cows.lower_bound({pos[u], -INF});
    int p = it->s;
    clean(loc[p].f);
    add(m, loc[p].f->val + 1);
    auto [lhs, rhs] = spliti(tour, order(loc[p].f) + 1);
    tour = merge(lhs, merge(m, rhs));
}

void insert(int u, ll x) {
    pos[u] = x;
    auto pit = prev(cows.lower_bound({x, -INF}));
    auto it = cows.lower_bound({pit->f - w, -INF});
    auto eit = cows.lower_bound({x - w, -INF});
    ptr mid = 0;
    auto cit = cows.lower_bound({x, -INF});
    if (it->f < eit->f && ((cit->f == x && cit->s > u) || cit->f > x)) {
        int in = order(loc[it->s].f);
        int out = order(loc[prev(eit)->s].s);
        ptr l, r;
        tie(l, mid, r) = cut(tour, in, out);
        tour = merge(l, r);
        int op = cit->s; // original parent
        clean(loc[op].f);
        add(mid, -loc[op].f->val - 1);
    }
    pit = cows.upper_bound({x + w, INF});
    int p = pit->s;
    clean(loc[p].f);
    int rd = loc[p].f->val + 1;
    add(mid, rd + 1);
    auto inn = new Node(rd);
    auto outn = new Node(rd);
    mid = merge(inn, merge(mid, outn));
    loc[u] = {inn, outn};
    auto nxt = cows.lower_bound({x, u});
    int si;
    if (nxt->f + w < pos[p]) si = order(loc[nxt->s].f); // before next child
    else si = order(loc[p].s); // end of children
    auto [lhs, rhs] = spliti(tour, si);
    tour = merge(lhs, merge(mid, rhs));
    cows.insert({x, u});
}

void build(int u, int d = 0) {
    ptr in = new Node(d);
    tour = merge(tour, in);
    loc[u].f = in;
    if (cows.lower_bound({pos[u], -INF})->s == u && pos[u] != -INF) {
        auto pit = prev(cows.lower_bound({pos[u], -INF}));
        auto it = cows.lower_bound({pit->f - w, -INF});
        auto eit = cows.lower_bound({pos[u] - w, -INF});
        while (it != eit) {
            build(it->s, d + 1);
            it++;
        }
    }
    ptr out = new Node(d);
    tour = merge(tour, out);
    loc[u].s = out;
}

void init(int N, int L, int X[]) {
    n = N + 2;
    w = L;
    pos.resize(n);
    loc.resize(n);
    F0R (i, n - 2) pos[i + 1] = X[i];
    pos[0] = -INF;
    pos[n - 1] = INF;
    F0R (i, n) cows.insert({pos[i], i});
    build(n - 1);
}

int update(int u, int y) {
    u++;
    erase(u);
    insert(u, y);
    push(tour);
    return agg(tour) - 1;
}

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