Submission #1184701

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184701		GGOSHAB	Dancing Elephants (IOI11_elephants)	C++20	100 / 100	3182 ms	8740 KiB

elephants

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

#define all(v) begin(v), end(v)

using namespace std;

int n, l;

using ll = long long;
const ll INF = (ll)1e18 + 10;
const int inf = 1e9 + 10;
const int maxn = 2e5 + 5;
int pos[maxn];

struct block {
    int n = 0;
    vector<ll> x = {}, last = {}, dp = {};
    block() {};
    void rebuild() {
        x.push_back(INF);
        last.assign(n + 1, -1);
        dp.assign(n + 1, 0);
        int j = n;
        for (int i = n - 1; i >= 0; --i) {
            while (j > 0 && x[i] + l < x[j - 1]) j--;
            last[i] = (j == n ? x[i] : last[j]);
            dp[i] = dp[j] + 1;
        }
        x.pop_back();
        last.pop_back();
        dp.pop_back();
    }
    void insert(int y) {
        auto it = lower_bound(all(x), y);
        x.insert(it, y);
        n++;
        rebuild();
    }
    void erase(int y) {
        auto it = lower_bound(all(x), y);
        x.erase(it);
        n--;
        rebuild();
    }
    void build_insert(int y) {
        n++;
        x.push_back(y);
    }
};

const int B = 100;
block b[maxn / B + 10];

int P;
void init(int N, int L, int X[]) {
    n = N;
    l = L;
    P = (n - 1) / B + 1;
    for (int i = 0; i < n; ++i) {
        pos[i] = X[i];
        b[i / B].build_insert(pos[i]);
    }
    for (int bl = 0; bl < P; ++bl) {
        b[bl].rebuild();
    }
}

int it = 0;
int update(int i, int y) {
    int bl = 0;
    for (int cur = 0; cur < P; ++cur) {
        if (b[cur].n != 0) {
            bl = cur;
            if (b[cur].x.back() >= pos[i]) {
                break;
            }
        }
    }
    b[bl].erase(pos[i]);
    pos[i] = y;
    bl = 0;
    for (int cur = 0; cur < P; ++cur) {
        if (b[cur].n != 0) {
            bl = cur;
            if (b[cur].x.back() >= pos[i]) {
                break;
            }
        }
    }
    b[bl].insert(pos[i]);

    ll res = 0, last = -INF;
    for (int bl = 0; bl < P; ++bl) {
        if (b[bl].n == 0) continue;;
        int i = upper_bound(all(b[bl].x), last + l) - b[bl].x.begin();
        if (i >= b[bl].n) continue;
        res += b[bl].dp[i];
        last = b[bl].last[i];
    }

    if (it++ > n / B) {
        for (int i = 0; i < P; ++i) {
            b[i] = {};
        }
        vector<int> p(n);
        iota(all(p), 0);
        sort(all(p), [](int i, int j) { return pos[i] < pos[j]; });
        for (int i = 0; i < n; ++i) {
            b[i / B].build_insert(pos[p[i]]);
        }
        for (int bl = 0; bl < P; ++bl) {
            b[bl].rebuild();
        }
        it = 0;
    }

    return res;
}

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