oj.uz

Submission #996924

# Submission time Handle Problem Language Result Execution time Memory
996924 2024-06-11T12:29:30 Z caterpillow Dancing Elephants (IOI11_elephants) C++17
100 / 100
 2001 ms 79996 KB 
#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.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 6592 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 303 ms 19136 KB Output is correct
8 Correct 318 ms 20408 KB Output is correct
9 Correct 481 ms 29012 KB Output is correct
10 Correct 338 ms 30816 KB Output is correct
11 Correct 365 ms 26916 KB Output is correct
12 Correct 514 ms 27868 KB Output is correct
13 Correct 395 ms 26960 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 6592 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 303 ms 19136 KB Output is correct
8 Correct 318 ms 20408 KB Output is correct
9 Correct 481 ms 29012 KB Output is correct
10 Correct 338 ms 30816 KB Output is correct
11 Correct 365 ms 26916 KB Output is correct
12 Correct 514 ms 27868 KB Output is correct
13 Correct 395 ms 26960 KB Output is correct
14 Correct 415 ms 23620 KB Output is correct
15 Correct 425 ms 25060 KB Output is correct
16 Correct 705 ms 32552 KB Output is correct
17 Correct 728 ms 37708 KB Output is correct
18 Correct 792 ms 35412 KB Output is correct
19 Correct 531 ms 35200 KB Output is correct
20 Correct 734 ms 37972 KB Output is correct
21 Correct 791 ms 35460 KB Output is correct
22 Correct 532 ms 33968 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 6592 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 303 ms 19136 KB Output is correct
8 Correct 318 ms 20408 KB Output is correct
9 Correct 481 ms 29012 KB Output is correct
10 Correct 338 ms 30816 KB Output is correct
11 Correct 365 ms 26916 KB Output is correct
12 Correct 514 ms 27868 KB Output is correct
13 Correct 395 ms 26960 KB Output is correct
14 Correct 415 ms 23620 KB Output is correct
15 Correct 425 ms 25060 KB Output is correct
16 Correct 705 ms 32552 KB Output is correct
17 Correct 728 ms 37708 KB Output is correct
18 Correct 792 ms 35412 KB Output is correct
19 Correct 531 ms 35200 KB Output is correct
20 Correct 734 ms 37972 KB Output is correct
21 Correct 791 ms 35460 KB Output is correct
22 Correct 532 ms 33968 KB Output is correct
23 Correct 1727 ms 74108 KB Output is correct
24 Correct 1773 ms 74172 KB Output is correct
25 Correct 1847 ms 74248 KB Output is correct
26 Correct 913 ms 71304 KB Output is correct
27 Correct 940 ms 71164 KB Output is correct
28 Correct 830 ms 35416 KB Output is correct
29 Correct 850 ms 35404 KB Output is correct
30 Correct 879 ms 35408 KB Output is correct
31 Correct 854 ms 35408 KB Output is correct
32 Correct 1192 ms 67668 KB Output is correct
33 Correct 904 ms 67052 KB Output is correct
34 Correct 1174 ms 79804 KB Output is correct
35 Correct 788 ms 79996 KB Output is correct
36 Correct 1012 ms 67720 KB Output is correct
37 Correct 1804 ms 79864 KB Output is correct
38 Correct 1386 ms 67136 KB Output is correct
39 Correct 1240 ms 69524 KB Output is correct
40 Correct 1311 ms 66908 KB Output is correct
41 Correct 1904 ms 75216 KB Output is correct
42 Correct 2001 ms 75624 KB Output is correct