Submission #542466

#	Time	Username	Problem	Language	Result	Execution time	Memory
542466		tabr	Dancing Elephants (IOI11_elephants)	C++17	97 / 100	9084 ms	7076 KiB

elephants

#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

const int MAX_N = 150015;
const int MAX_B = 810;
int B;
int n;
int l;
int upd_cnt;
int x[MAX_N];
int pos[MAX_N];
int jump_cnt[MAX_N];
int jump_pos[MAX_N];
int e[MAX_B][MAX_B];
int sz[MAX_B];
int order[MAX_N];

void init(int n_, int l_, int x_[]) {
    n = n_;
    l = l_;
    B = (int) sqrt(n_ * (n <= 1000 ? 1 : 0.8));
    for (int i = 0; i < n; i++) {
        x[i] = x_[i];
    }
    iota(order, order + n, 0);
}

void build_one(int id) {
    sort(e[id], e[id] + sz[id], [&](int i, int j) {
        return x[i] < x[j];
    });
    for (int i = 0; i < sz[id]; i++) {
        pos[e[id][i]] = id;
    }
    for (int i = sz[id] - 1, j = sz[id]; i >= 0; i--) {
        while (j > 0 && x[e[id][j - 1]] > x[e[id][i]] + l) {
            j--;
        }
        if (j == sz[id]) {
            jump_cnt[e[id][i]] = 1;
            jump_pos[e[id][i]] = x[e[id][i]] + l + 1;
        } else {
            jump_cnt[e[id][i]] = jump_cnt[e[id][j]] + 1;
            jump_pos[e[id][i]] = jump_pos[e[id][j]];
        }
    }
}

void build() {
    sort(order, order + n, [&](int i, int j) {
        return x[i] < x[j];
    });
    for (int i = 0; i < B; i++) {
        sz[i] = 0;
        for (int j = n * i / B; j < n * (i + 1) / B; j++) {
            e[i][sz[i]] = order[j];
            sz[i]++;
        }
        build_one(i);
    }
}

int update(int i, int y) {
    if (n == 1) {
        return 1;
    }
    if (upd_cnt == 0) {
        build();
    }
    upd_cnt++;
    if (upd_cnt == n / B - 1) {
        upd_cnt = 0;
    }
    // remove x[i]
    for (int j = 0; j < sz[pos[i]] - 1; j++) {
        if (e[pos[i]][j] == i) {
            e[pos[i]][j] = e[pos[i]][sz[pos[i]] - 1];
            break;
        }
    }
    sz[pos[i]]--;
    build_one(pos[i]);
    // add x[i]
    x[i] = y;
    for (int id = 0; id < B; id++) {
        if (id == B - 1 || x[e[id + 1][0]] > y) {
            e[id][sz[id]] = i;
            sz[id]++;
            build_one(id);
            break;
        }
    }
    // answer
    int ans = 0;
    int now = 0;
    for (int id = 0; id < B; id++) {
        x[150001] = now;
        auto iter = lower_bound(e[id], e[id] + sz[id], 150001, [&](int j, int k) {
            return x[j] < x[k];
        });
        if (iter == e[id] + sz[id]) {
            continue;
        }
        ans += jump_cnt[*iter];
        now = jump_pos[*iter];
    }
    return ans;
}

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n_ = 4;
    int l_ = 10;
    int x_[10];
    x_[0] = 10;
    x_[1] = 15;
    x_[2] = 17;
    x_[3] = 20;
    init(n_, l_, x_);
    debug(update(2, 16));  // 1
    debug(update(1, 25));  // 2
    debug(update(3, 35));  // 2
    debug(update(0, 38));  // 2
    debug(update(2, 0));   // 3
    return 0;
}
#endif

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